题解 P1561 【[USACO12JAN]爬山Mountain Climbing】

unicornshjl · 2019-12-01 19:40:46 · 题解

USACO的题解都很少呢，我来发一发

9102年，P党的人更少了，我来帮助 （拯救）一波P党。

题目意思非常地清楚，毕竟连我这样的语文白痴都看懂了。

那么我们开始讲思路吧！

贪心

本蒟蒻看到好多题解都用了排序，其实没有必要呀，我们只需要分别统计奶牛上山和下山的时间之和，以及分别找出奶牛上山和下山时间的最小值，最后在上山时间和与下山最小值之和以及下山时间和与上山时间最小值之和找个最小值输出就行了。

可以想想正确性的证明，这里就不证明了，毕竟有一篇题解里写出了详细的过程，我的貌似没有ta的详细哇qaq

最后帖代码吧

var n,i,x1,y1,x2,y2,x,y:longint;
function min(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end;
begin
readln(n);
x1:=maxlongint;y1:=maxlongint;
for i:=1 to n do
  begin
  readln(x,y);
  if x1>x then x1:=x;
  if y1>y then y1:=y;
  x2:=x2+x;y2:=y2+y;
  end;
writeln(min(x2+y1,x1+y2));
end.

蒟蒻的tips：千万别csp的时候用uses math 啊，会抱零的。

来自一位已经退役的选手。管理员大大求过