P1561 [USACO12JAN] Mountain Climbing S

传送门题目描述约翰农夫发现他的奶牛在进行剧烈运动时会产出更高质量的牛奶。因此他决定让他的N NN头奶牛1 ≤ N ≤ 25 , 000 1 \le N \le 25,0001≤N≤25,000去爬一座附近的山然后再下来第i ii头奶牛需要U ( i ) U(i)U(i)的时间爬上山然后需要D ( i ) D(i)D(i)的时间爬下山。由于奶牛是家养的每头奶牛在爬山的每一段路程中都需要农夫的帮助但由于经济不景气只有两位农夫可用即约翰农夫和他的表弟唐农夫。约翰农夫计划指导奶牛上山而唐农夫将指导奶牛下山。由于每头奶牛都需要一个向导并且每段旅程中只有一位农夫因此在任何时间点最多只有一头奶牛可以在约翰农夫的帮助下爬上山最多只有一头奶牛可以在唐农夫的帮助下爬下山。奶牛可能会在山顶暂时聚集如果它们爬上山后需要等待唐农夫的帮助才能下山。奶牛下山的顺序可以与上山的顺序不同。请确定所有N NN头奶牛完成整个旅程所需的最短时间。输入格式第一行一个整数N NN。第2 22到第N 1 N1N1行每行两个用空格隔开的整数U ( i ) U(i)U(i)和D ( i ) D(i)D(i)。( 1 ≤ U ( i ) , D ( i ) ≤ 50 , 000 ) (1 \le U(i),D(i) \le 50,000)(1≤U(i),D(i)≤50,000)。输出格式一行一个整数表示所有N NN头奶牛完成旅程的最短时间。输入输出样例 #1输入 #13 6 4 8 1 2 3输出 #117思路考虑贪心算法此题就是因为证明难度大才评为紫题作者比较菜所以不会证但代码较简单。代码#includebits/stdc.husingnamespacestd;intn;structdid{inta,b;}p[30001];boolcmp(did x,did y){if(x.ax.b){if(y.ay.b)returnx.ay.a;return1;}else{if(y.ay.b)return0;returnx.by.b;}}intmain(){cinn;for(inti1;in;i)cinp[i].ap[i].b;sort(p1,p1n,cmp);intA0,B0;for(inti1;in;i){Ap[i].a;if(BA)BA;Bp[i].b;}coutB;return0;}注意此题还有多倍经验。P1248B4156P2123P6243