Codeforces Round #433 (Div. 2) C. Planning(贪心)
发布日期:2021-08-17 20:35:00 浏览次数:1 分类:技术文章

本文共 933 字,大约阅读时间需要 3 分钟。

题目链接:

题意:

有n架飞机要起飞,起飞的时间是t1=k+1,t2=k+2...tn=k+n。

现在有n个位置,每个位置的cost为(t-i)*ai(t>=i),现在问你如何给每架飞机安排位置,使得sumcost最小。

题解:

考虑贪心,先将a从大到小排序,显然对于大的a,乘的数越小越好,然后用set搞一搞就行了。

1 #include
2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 typedef long long ll; 5 typedef pair
P; 6 7 const int N=3e5+7; 8 multiset
st; 9 int n,k,ans[N];10 P a[N];11 ll ret=0;12 int main(){13 scanf("%d%d",&n,&k);14 F(i,1,n)scanf("%d",&a[i].first),a[i].second=i;15 sort(a+1,a+1+n,greater

());16 F(i,1,n)st.insert(k+i);17 F(i,1,n)18 {19 auto it=st.lower_bound(a[i].second);20 ans[a[i].second]=*it;21 ret+=(ll)(*it-a[i].second)*a[i].first;22 st.erase(it);23 }24 printf("%lld\n",ret);25 F(i,1,n)printf("%d%c",ans[i]," \n"[i==n]);26 return 0;27 }

View Code

 

转载于:https://www.cnblogs.com/bin-gege/p/7489143.html

转载地址:https://blog.csdn.net/weixin_30867015/article/details/96617543 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:javascript学习导图
下一篇:hdu 3480 Division(斜率优化DP)

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2024年03月04日 13时41分25秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

linux 网络音箱 混音6,Linux音频编程(三)混音器介绍 2019-04-21
node与mysql开源_node与mysql的相互使用————node+mysql 2019-04-21
python合并列表重新排序_python – 将两个已排序的列表合并为一个更大的排序列表... 2019-04-21
vbs用mysql语句查询数据库_vbs脚本实现window环境下的mysql数据库的备份及删除早期备份... 2019-04-21
mysql连接nginx_nginx四层负载均衡连接mysql 2019-04-21
mysql截取栏目字符_substring从指定字符串开始截取(图) 2019-04-21
python 函数参数前面两个星号_Python中参数前面一个星号两个星号(*参数,**参数)起什么作用呢?... 2019-04-21
python类属性初始化_Python类定义、属性、初始化和析构 2019-04-21
mysql构建url给scrapy_Python Scrapy从mysq填充起始url 2019-04-21
owdcloud mysql_MySQL在Ubuntu远程配置 2019-04-21
python基础装饰器_Python基础 装饰器及练习 2019-04-21
python导出csv不带引号的句子_不带双引号写入CSV文件 2019-04-21
python爬虫代码模板_Python:学习Python爬虫的第一天 2019-04-21
springboot获取原生js请求_springboot跳转原生html 2019-04-21
java buffer nio_Java NIO之Buffer(缓冲区)入门 2019-04-21
android java加密_android 和java平台通用的AES加密解密 2019-04-21
java导出类_java导出excel工具类 2019-04-21
java学习手册下载_Java学习手册 2019-04-21
axios delete有请求体吗_关于axios请求——delete方法 2019-04-21
java 自助更改密码 api_搭建ldap自助修改密码系统--Self Service Password 2019-04-21