(以“ 分类:贪心 ==摘要== {{信息题|Printed PR|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}259|1|100|time=2015-2-5 21:08:35}} (AC 1371) ==题...”为内容创建页面)
 
题解: 回退排版
 
(未显示1个用户的1个中间版本)
第40行: 第40行:
 
   因为max(Lc-Td,Ld)>max(Ld-Tc,Lc),
 
   因为max(Lc-Td,Ld)>max(Ld-Tc,Lc),
 
   所以 c,d 互换,即d排在c之前,解为最优解 。
 
   所以 c,d 互换,即d排在c之前,解为最优解 。
 +
 
==代码==
 
==代码==
 
{{折叠|259.cpp代码已折叠
 
{{折叠|259.cpp代码已折叠

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

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 需要注意
Printed PR ★☆☆☆☆ 答案正确 100 2015-2-5 21:08:35

(AC 1371)

题意

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

题解

直觉是贪心,相比较Ti排序、\frac{Ti}{Li}排序,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之前,解为最优解 。

代码

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


参考资料和拓展阅读

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

著作权声明[编辑]

关于[编辑]