HDU 4296 Buildings（12年成都网络赛-贪心）

题目链接：Click here~~

题意：

有 n 个地板，每个地板 i 有两个权值 Wi, Si，且 PDV(i) = (ΣW_{j) - Si ( j 表示在 i 上面的地板)。问如何调整顺序，使得【max(PDV)】最小。}

解题思路：

假设现在有 i、j 两个地板需要安排顺序。

若 i 在上，Pi = -Si，Pj = Wi - Sj。

若 j 在上，Pi' = Wj - Si，Pj' = -Sj。

显然有 Pi <= Pi'，那么若 Pj <= Pi'，则 max(Pi,Pj) <= Pi' <= max(Pi',Pj')。

即 Wi+Si <= Wj+Sj 时，i 在上更能使结果变小。

由此可推出，n 个地板时，按 Wi+Si 递增的顺序排列，max(PDV) 最小，且由上面的递推式可以看出，max(PDV)一定在最下面那层。

#include <stdio.h>#include <algorithm>using namespace std;int main(){    int n,w,s;    while(~scanf("%d",&n))    {        int mmax = 0;        __int64 sum = 0;        while(n--)        {            scanf("%d%d",&w,&s);            sum += w;            mmax = max(mmax,s+w);        }        printf("%I64d\n",sum-mmax<0 ? 0 : sum-mmax);    }    return 0;}

Ps：这题的数据随机了那么多竟然没随机出为负数的情况。Orz。