Hdu 4296 building.cpp-白红宇

Hdu 4296 building.cpp

阅读量：4972 次

发布时间：2019-06-12

本文共 1235 字，大约阅读时间需要 4 分钟。

题意：

给出 n 个木板的重量值和长度然后每个木板的PDV = 压在他上面的木板的重量值之和-该木板的长度值

求所有木板中PDV值最大的最小

给出一个 n 表示木板的数量

接下来 n 行表示每块木板的重量值和长度值

求PDV最大的最小

思路：

按最优方法排序然后求最大值

Tips：

①如果排序为 a b 则a的PDV = sum-sb b的PDV = sum+wa-sb

②如果排序为 b a 则b的PDV = sum-sa a的PDV = sum+wb-sa

要想第一种方法要想最大值的PDV < 第二种方法最大值

则 wa+sa < wb+sb

所以排序然后找这种最优方法中的最大值

Code：

View Code

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 #define max(a, b) ((a)>(b)?(a):(b)) 6 const int INF = 0x1f1f1f1f; 7  8 struct Floor 9 {10     int w;11     int s;12 }floor[100010];13 14 int cmp(Floor a, Floor b)15 {16     return a.w+a.s < b.w+b.s;17 }18 19 int main()20 {21     int i, j, k;22     int n;23     long long ans, sum;24     while(scanf("%d", &n) != EOF)25     {26         ans = -100000000, sum = 0;27 28         for(i = 0; i < n; ++i) {29             scanf("%d %d", &floor[i].w, &floor[i].s);30         }31 32         sort(floor, floor+n, cmp);33 34         for(i = 0; i < n; ++i) {35             if(i != 0) ans = max(ans, sum-floor[i].s);36             sum += floor[i].w;37         }38 39         printf("%I64d\n", ans<0?0:ans);40     }41     return 0;42 }