「Poetize10」封印一击
2024-10-16 05:55:47
描述 Description
Nescafe由n种元素组成(编号为1~n), 第i种元素有一个封印区间[ai,bi]。当封印力度E小于ai时,该元素将获得ai的封印能量;当封印力度E在ai到bi之间时,该元素将获得E的封印 能量;而当封印力度E大于bi时,该元素将被破坏从而不能获得任何封印能量。现在圣主applepi想选择恰当的E,使得封印获得的总能量尽可能高。为了 封印的最后一击尽量完美,就请你写个程序帮他计算一下吧!
题解:
首先必须离散化,然后差分可以算出在区间外且<a[i]的总得分,再差分一次可以算出每个点被区间覆盖了几次,然后就是统计了。
代码:
首先必须离散化,然后差分可以算出在区间外且<a[i]的总得分,再差分一次可以算出每个点被区间覆盖了几次,然后就是统计了。
代码:
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> #include<vector> #include<map> #include<set> #include<queue> #include<string> #define inf 1000000000 #define maxn 1000000
#define maxm 500+100 #define eps 1e-10 #define ll long long #define pa pair<int,int> #define for0(i,n) for(int i=0;i<=(n);i++) #define for1(i,n) for(int i=1;i<=(n);i++) #define for2(i,x,y) for(int i=(x);i<=(y);i++) #define for3(i,x,y) for(int i=(x);i>=(y);i--) #define mod 1000000007 using namespace std; inline int read() { int x=,f=;char ch=getchar(); while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();} while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();} return x*f; }
struct rec{ll x,y;}b[maxn];
ll n,a[maxn],s[][maxn],c[maxn];
inline bool cmp(rec a,rec b){return a.x<b.x;} int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); n=read();
for1(i,n)a[(i<<)-]=read(),a[i<<]=read();
for1(i,n<<)b[i].x=a[i],b[i].y=i;
sort(b+,b+*n+,cmp);
int tot=;
for1(i,n<<)
{
if(i==||b[i].x!=b[i-].x)tot++;
a[b[i].y]=tot;c[tot]=b[i].x;
}
for1(i,n)
{
int l=a[(i<<)-],r=a[i<<];
s[][]+=c[l];s[][l]-=c[l];
s[][l]++;s[][r+]--;
}
int ans=;
for1(i,tot+)
{
s[][i]+=s[][i-];s[][i]+=s[][i-];
if(s[][i]+s[][i]*c[i]>s[][ans]+s[][ans]*c[ans])ans=i;
}
printf("%lld %lld\n",c[ans],s[][ans]+s[][ans]*c[ans]);
return ; }
最新文章
- ng-class的用法
- 转载--How to Install VMware Tools on CentOS 6.3
- exp.validate.js
- 插件框架(Plugin Framework)
- ab 测试模块高并发
- Hibernate基于注解方式配置来实现实体和数据库之间存在某种映射关系
- 首先,定义一个Print类,它有一个方法void output(int x),如果x的值是1,在控制台打印出大写的英文字母表;如果x的值是2,在 控制台打印出小写的英文字母表。其次,再定义一个主类——TestClass,在主类 的main方法中创建Print类的对象,使用这个对象调用方法output ()来打印出大 小写英文字母表。
- session的介绍与简单使用
- Ubuntu下将vim配置为Python IDE(转)
- 次小生成树学习+例题 poj 1679 The Unique MST
- for/range/break/continue
- Android 上传图片到服务器 okhttp一
- spring boot+mybatis+generator生成domain大小写问题
- JavaScript基础笔记(三) 引用类型
- JSONModel(I)
- 关不掉的小姐姐程序python tkinter实现 学习---打包教程
- 洛谷 P2515 [HAOI2010]软件安装 解题报告
- Java int转string 长度不足左补0
- 判断python字典中key是否存在
- qt 5.2.1类和模块的关系图
热门文章
- SQL 约束解说
- [置顶] UNIX常用命令
- spring mvc DispatcherServlet详解之前传---前端控制器架构
- Java EE的十三种核心技术
- Another app is currently holding the yum lock; waiting for it to exit... 怎么解决
- Vijos P1325桐桐的糖果计划(有向图双连通分量)
- codevs 1183 泥泞的道路 (二分+SPFA+差分约束)
- expdp 备份数据库-附带报错信息
- 小试牛刀-嘿嘿,创建job了
- UIView ->; image &; 本地时间获取