题目链接:Click here~~
题意:
有 n 个地板,每个地板 i 有两个权值 Wi, Si,且 PDV(i) = (ΣWj)
- 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。