封印一击 Seal

2019-11-11 02:50:38

字体：大中小

来源：转载

供稿：网友

封印一击

(seal.pas/c/cpp)

题目描述

“圣主 applepi 于公元 2011 年 9 月创造了 Nescafe，它在散发了 16 次光辉之后与公元2011 年 11 月 12 日被封印为一颗魂珠，贮藏于 Nescafe 神塔之中。公元 2012 年 9 月，圣主带领四大护法重启了 Nescafe，如今已经是 Nescafe 之魂的第 30 次传播了。不久，它就要被第二次封印，而变成一座神杯……”applepi 思索着 Nescafe 的历史，准备着第二次封印。 Nescafe 由 n 种元素组成（编号为 1~n），第 i 种元素有一个封印区间[ai,bi]。当封印力度E 小于 ai 时，该元素将获得 ai 的封印能量；当封印力度 E 在 ai 到 bi 之间时，该元素将获得E 的封印能量；而当封印力度 E 大于 bi 时，该元素将被破坏从而不能获得任何封印能量。现在圣主 applepi 想选择恰当的 E，使得封印获得的总能量尽可能高。为了封印的最后一击尽量完美，就请你写个程序帮他计算一下吧！

输入格式

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

输出格式

两个用空格隔开的整数，第一个数是能够获得最多总能量的封印力度 E，第二个数是获得的总能量大小。当存在多个 E 能够获得最多总能量时，输出最小的 E。

样例输入

2 5 10 20 25

样例输出

10 30

数据范围与约定

对于 50% 的数据，1<=N<=1000，1<=ai<=bi<=10000。对于 100% 的数据，1<=N<=10^5，1<=ai<=bi<=10^9。

思路想对了，没敢写，暴力50分，果然是做题太少了。

正解思路：

很容易想到，最优解的E肯定是某个区间的端点！所以我们把所有区间的左右端点取出，从小到大排序，扫描一遍。维护一个变量sa，表示扫描到的值为p时，左端点大于p的所有区间的左端点之和；维护一个变量sp，表示扫描到的值为p时，p在左右端点之间的区间个数。那么此时可以封印一击得到的能量就是sa+sp*p。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;struct node{int x,y;}c[200010];int a[100010],b[100010],n,i,p;long long sa,sp,ans;bool cmp(const node & a,const node & b){return a.x<b.x||a.x==b.x&&a.y>b.y;}int main(){ freopen("seal.in","r",stdin); freopen("seal.out","w",stdout); cin>>n; for(i=1;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); sa+=a[i];//sa:suma c[i].x=a[i],c[i].y=1; c[n+i].x=b[i],c[n+i].y=-1; } sort(c+1,c+2*n+1,cmp); for(i=1;i<=2*n;i++) if(c[i].y==1) { sp++,sa-=c[i].x; if(ans<sa+sp*c[i].x) ans=sa+sp*c[i].x,p=c[i].x; } else { if(ans<sa+sp*c[i].x) ans=sa+sp*c[i].x,p=c[i].x; sp--; } cout<<p<<' '<<ans<<endl; return 0;}

上一篇：500. Keyboard Row

下一篇：数据结构实验之二叉树三：统计叶子数

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注