当前位置:编程学习 > C/C++ >>

TYVJ P2065(区间嵌套与统计)

P2065 - 「Poetize10」封印一击
From lydliyudong    Normal (OI)
总时限:10s    内存限制:128MB    代码长度限制:64KB
背景 Background

“圣主applepi于公元2011年9月创造了Nescafe,它在散发了16次光辉之后与公元2011年11月12日被封印为一颗魂珠,贮藏于Nescafe神塔之中。公元2012年9月,圣主带领四大易做图重启了Nescafe,如今已经是Nescafe之魂的第30次传播了。不久,它就要被第二次封印,而变成一座神杯……”applepi思索着Nescafe的历史,准备着第二次封印。 www.zzzyk.com
描述 Description

Nescafe由n种元素组成(编号为1~n),第i种元素有一个封印区间[ai,bi]。当封印力度E小于ai时,该元素将获得ai的封印能量;当封印力度E在ai到bi之间时,该元素将获得E的封印能量;而当封印力度E大于bi时,该元素将被破坏从而不能获得任何封印能量。现在圣主applepi想选择恰当的E,使得封印获得的总能量尽可能高。为了封印的最后一击尽量完美,就请你写个程序帮他计算一下吧!
输入格式 InputFormat

第一行一个整数N。
接下来N行每行两个整数ai、bi,第i+1行表示第i种元素的封印区间。
输出格式 OutputFormat

两个用空格隔开的整数,第一个数是能够获得最多总能量的封印力度E,第二个数是获得的总能量大小。当存在多个E能够获得最多总能量时,输出最小的E。
样例输入 SampleInput [复制数据]

2
5 10
20 25
样例输出 SampleOutput [复制数据]

10 30
数据范围和注释 Hint

对于 50% 的数据,1<=N<=1000,1<=ai<=bi<=10000。
对于 100% 的数据,1<=N<=10^5,1<=ai<=bi<=10^9。
时间限制 TimeLimitation

各个测试点1s
区间选取
用Past和In_s维护经过的左右结点,
并由此算出
嵌套数(左-右)
左边的区间数=右
右边的区间数=总-(左-右)-右=总-左

PS:由于是闭区间,需要把-右的时间后延

[cpp] 
#include<cstdio> 
#include<cstdlib> 
#include<cstring> 
#include<cmath> 
#include<cctype> 
#include<iostream> 
#include<functional> 
#include<algorithm> 
using namespace std; 
#define MAXN (200000+10) 
#define MAXAi (1000000000) 
#define NDEBUG 
struct segment_node 

    int l,type; 
    friend bool operator<(const segment_node a,const segment_node b){return (a.l!=b.l)?a.l<b.l:a.type<b.type;  } 
    friend bool operator==(const segment_node a,const segment_node b){return (a.l==b.l&&a.type==b.type);    } 
    friend bool operator!=(const segment_node a,const segment_node b){return (!(a==b)); } 
     
}a[MAXN]; 
int n; 
long long next[MAXN]; 
int main() 

    #ifndef NDEBUG 
    freopen("segmentbet.in","r",stdin); 
    #endif 
    memset(a,0,sizeof(a)); 
    scanf("%d",&n);n<<=1; 
    for (int i=1;i<=n;i+=2) 
    { 
        scanf("%d%d",&a[i].l,&a[i+1].l); 
        a[i].type=-1;a[i+1].type=1; 
    }    
    sort(a+1,a+n+1); 
    int in_s=0,minE=0; 
    long long ans=0; 
    memset(next,0,sizeof(next)); 
    for (int i=n-1;i>=1;i--)  
    { 
        next[i]=next[i+1]; 
        if (a[i+1].type==-1)  
            next[i]+=a[i+1].l;   
    } 
    int j=1,past=0,pastE=0; 
    for (int i=1;i<=n;i++) 
    { 
        if (a[i]!=a[i+1]) 
        { 
            int len=i-j+1; 
            j=i+1; 
            len*=-a[i].type; 
            if (pastE!=a[i].l) {in_s+=past;past=0;} 
            if (len>0) in_s+=len; 
            else past+=len; 
                         
            long long cost=(long long)(long long)in_s*(long long)a[i].l+next[i]; 
            if (ans<cost) 
            { 
                ans=cost; 
                minE=a[i].l; 
            }        
                                     
        } 
                 
    } 
    cout<<minE<<' '<<ans<<endl; 
    return 0; 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,