“Sgu/259”的版本间的差异

2015年2月5日 (四) 21:17的最后版本

摘要

（AC 1371）

题意

一堆海报，必需先印刷（需时Ti，不可并行）后分发（需时L，可并行），求所有事情搞定的最短时间。

题解

直觉是贪心，相比较Ti排序、排序，Li排序比较靠谱，试下的确也就A了。

However贪心是需要证明的。直观来说的确不太好想，不过我们可以看一下答案是怎么算的。

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之前，解为最优解 。

代码

#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;
}

参考资料和拓展阅读

1. ↑ http://blog.csdn.net/u012139398/article/details/43445383