【Python3】【贪心】hdu4296 Buildings

题意：

n个板，每个板有重量和强度w和s，还有PDV值（上面的总重量-该板的强度）

对于某种叠放方式，PDV的最大值为其代表值

求该值的最小值

 

考虑只有两个板的情况：a和b，很显然下面的比上面的容易损坏，所以下面的PDV大。假设a在上面，其PDV值 = pdvb = wa - sb。假设b在上面，其PDV值 = pdva = wb - sa。然后两个值取最小，若a在上面的PDV小，则 wa - sb < wb - sa，即wa + sa < wb + sb。同理，若b在上面的PDV小，则wb + sb < wa + sa。

扩展到有n个板的情况，任意两个相邻的板不对其他板产生影响，于是按照w+s从小到大排序，自顶向下排列即可。

try:

    while True:

        n = input();

        n = int(n);

        a = [];

        for i in range(0, n):

            str = input().split();

            a += [[int(str[0]), int(str[1])]];

        a = sorted(a, key = lambda x: x[0]+x[1]);

        sumv = 0;

        maxx = 0;

        for i in range(0, n):

            maxx = max(maxx, sumv-a[i][1]);

            sumv += a[i][0];

        print(maxx);

except EOFError:

    pass