题意:有n(1<=n<=100000)块地板,每块有wi自身重量和si承重重量,每一块地板有对应的PDV = sum(wj above) - si,
现在想安排一种摆放方案使得max(PDVi)最小。
题解:现在考虑相邻的两块i j,设上方sigama(wi) = sum,i 在 j上方时分别得到PDVi = sum - si,PDVj = sum + wi - sj,同理得到j在i上方时
PDVjj = sum - sj,PDVii = sum + wj - si,若i在j上方始终优于j在i上方,则MAX(PDVi , PDVj) < MAX(PDVii , PDVjj),
推出wi + si < wj + sj 为i在j上方的解更优的充要条件。所以可以推出从上到下i + si递减为最优解,此时最下面的PDV最大。
Sure原创,转载请注明出处。
#include <iostream> #include <cstdio> using namespace std; int n; inline void in(long long &a) { char ch; while(ch = getchar(), ch < '0' || ch > '9'); a = ch - '0'; while(ch = getchar(), ch >= '0' && ch <= '9') { a = a * 10 + ch - '0'; } return; } void solve() { long long sum = 0,s = 0; long long x,y; for(int i=0;i<n;i++) { in(x),in(y); sum += x; if(x + y > s) s = x + y; } printf("%I64d\n",sum-s); return; } int main() { while(~scanf("%d",&n)) { solve(); } return 0; }