2018.09.16 atcoder Garbage Collector(贪心)
2024-10-18 22:31:29
传送门
昨晚打比赛的时候不是很机智啊。
这道题贪心就能过了。
我们可以发现一个明显的结论,每次选的垃圾的距离从大到小排序之后,每个距离对答案的贡献的系数是5,5,7,9,11…也就是最远的是5,其余都是2*rank+1。
这样就可以根据每次选几个垃圾来贪心。
代码:
#include<bits/stdc++.h>
#define ll long long
#define N 200005
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n;
ll ans=1e18,X,x[N],sum[N];
int main(){
n=read(),X=read();
for(int i=1;i<=n;++i)sum[i]=(x[i]=read())+sum[i-1];
for(int k=1;k<=n;++k){
ll tmp=0;
for(int j=1,l=0,r=n;r&&tmp+k*X<ans;++j,r=l-1){
l=max(r-k+1,1);
tmp+=(j==1?5:(j<<1)+1)*(sum[r]-sum[l-1]);
}
ans=min(ans,tmp+k*X);
}
printf("%lld",ans+n*X);
return 0;
}
最新文章
- Revit读取当前rvt的所有视图与其名称
- Eos持久化实体
- python类——黑板客老师课程学习
- Microsoft Dynamics CRM 2013 --选项集的多选
- c/c++ 笔试面试题
- 参数db_ultra_safe
- for循环的嵌套——7月24日
- android学习笔记32——资源
- vector 与 set区别
- C语言判断文件是否存在
- Objective-C中instancetype和id的区别
- UILable文本常见属性说明
- java中int,char,string三种类型的相互转换
- Visual Leak Detector(vld)无法显示内存泄露文件名称与行号
- window.print打印指定html元素中的内容
- 3.QT中QCommandLineParser和QCommandLineOption解析命令行参数
- Server Tomcat v7.0 Server at localhost failed to start.解决办法
- MyBatis - 4.动态SQL
- SparkSQL与Hive on Spark的比较
- _rank