| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
|---|---|---|---|---|---|
| Printed PR | ★☆☆☆☆ | 答案正确 | 100 | 2015-2-5 21:08:35 | 无 |
（AC 1371）
一堆海报，必需先印刷（需时Ti，不可并行）后分发（需时L，可并行），求所有事情搞定的最短时间。
直觉是贪心，相比较Ti排序、排序，Li排序比较靠谱，试下的确也就A了。
However贪心是需要证明的。直观来说的确不太好想，不过我们可以看一下答案是怎么算的。
CloudLunar
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;
很明显，越前的时候，lastPrint越小，可以用来抵消更大的Li。而越后面，直到最后一步，lastPrint是一定的，Li一定越小越好。
下面Copy一段严谨一点的证明[1]：
#证明：
#(对于仅有两个对象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代码已折叠
展开折叠内容
|
|---|
#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;
}
|