CloudLunar
主页
知识库
人文社科
自然科学
跨学科领域
热门分类
算法及题库
云璟月's
墨色集(设计)
指尖集(代码)
未央集(随笔)
流觞集(语录)
如花集(书影)
纸鸢集(小说)
登录
B站
微博
人人
开心
Twitter
Facebook
RSS订阅链接
留言板
关于我
在社交网站上关注我
B站
微博
人人
开心
Twitter
Facebook
RSS订阅
RSS订阅链接
留言板
关于我
查看Sgu/259的源代码
←
Sgu/259
因为以下原因,你没有权限编辑本页:
你刚才请求的操作只对属于该用户组的用户开放:
用户
您可以查看并复制此页面的源代码:
[[分类:贪心]] ==摘要== {{信息题|Printed PR|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}259|1|100|time=2015-2-5 21:08:35}} (AC 1371) ==题意== 一堆海报,必需先印刷(需时Ti,不可并行)后分发(需时L,可并行),求所有事情搞定的最短时间。 ==题解== 直觉是贪心,相比较Ti排序、<m>\frac{Ti}{Li}</m>排序,Li排序比较靠谱,试下的确也就A了。 However贪心是需要证明的。直观来说的确不太好想,不过我们可以看一下答案是怎么算的。 <pre> int lastPrint=0,lastAll=0; for(int i=1;i<=n;++i) { lastPrint+=a[i].t; lastAll=max(lastAll,lastPrint+a[i].l); } cout<<lastAll; </pre> 很明显,越前的时候,lastPrint越小,可以用来抵消更大的Li。而越后面,直到最后一步,lastPrint是一定的,Li一定越小越好。 下面Copy一段严谨一点的证明<ref>http://blog.csdn.net/u012139398/article/details/43445383</ref>: #证明: #(对于仅有两个对象a,b时) 若Lb<La则Lb-Ta<La; 于是La>max(Lb,La-Tb),其中: La 为b在a前边 max(Li-(Ti+1 +...+Tn)) 的情况; max(L(b,La-Tb) 为a在b前边 max(Li-(Ti+1 +...+Tn)) 的情况; 因此a排在b的前边更优; 即当Lb<La时a应排在b的前边。 #(对于多个对象时) 设c,d为序列中的两个; 设c排在d前,则Lc<Ld; c在d前时为 max(Lc -Td -(Td+1 +......+Tn),Ld-(Td+1+........TN)); c,d互换时为 max(Ld-Tc-(Td+1+....+Tn),Lc-(Td+1+......Tn)); 因为max(Lc-Td,Ld)>max(Ld-Tc,Lc), 所以 c,d 互换,即d排在c之前,解为最优解 。 ==代码== {{折叠|259.cpp代码已折叠 |<pre> #include<cstdio> #include<algorithm> #include<iostream> using namespace std; class j { public : int t,l; friend bool operator <(const j&_a,const j&_b) { return _a.l>_b.l; } } a[1000000]; int main() { int n; cin>>n; for(int i=1;i<=n;++i) cin>>a[i].t; for(int i=1;i<=n;++i) cin>>a[i].l; sort(a+1,a+n+1); int lastPrint=0,lastAll=0; for(int i=1;i<=n;++i) { lastPrint+=a[i].t; lastAll=max(lastAll,lastPrint+a[i].l); } cout<<lastAll; return 0; } </pre> |sgu259}} ==参考资料和拓展阅读== <references/>
该页面使用的模板:
模板:=
(
查看源代码
)
模板:信息题
(
查看源代码
)
模板:折叠
(
查看源代码
)
返回
Sgu/259
。
著作权声明
[
编辑
]
除非另有说明,本
网站内容
采用
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议
进行许可(中国大陆可以参照
知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议
,如有不同以前者为准)。
如果需要商业化使用,请另联系作者取得授权。
关于
[
编辑
]
联系
@云璟月Lunar
的新浪微博
本站RSS:
RSS链接