查看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/>