1，
给定平面上n个OIer和n台电脑，每个OIer只能水平向右和竖直向下，找到一台电脑写代码，其花费为OIer与电脑之间的曼哈顿距离(|x_i-x_j|+|y_i-y_j|)。
求出使n个OIer均找到自己电脑的最小花费。
输入输出格式 Input/output输入格式：
输入第1行有一个整数n，表示点的个数。
接下来有n行，第i行包括两个用空格隔开的整数x_i,y_i，表示第i个OIer的位置；
接下来有n行，第i行包括两个用空格隔开的整数x_i,y_i，表示第i台电脑的位置。
输出格式：
输出1个整数，表示最小花费。
输入第1行有一个整数n，表示点的个数。
接下来有n行，第i行包括两个用空格隔开的整数x_i,y_i，表示第i个OIer的位置；
接下来有n行，第i行包括两个用空格隔开的整数x_i,y_i，表示第i台电脑的位置。
输出格式：
输出1个整数，表示最小花费。
输入输出样例 Sample input/output
输入样例：
2
2
1 2
1 3
2 2
2 3
输出样例：
2
2
说明 description对于样例，第一个OIer寻找到第一台电脑，第二个OIer寻找到第二台电脑。
最小花费为|2-1|+|2-2|+|2-1|+|3-3|=2。
对于30%的数据，保证2≤n≤50；
对于60%的数据，保证2≤n≤10^3；
对于100%的数据，保证2≤n≤5×10^4，0≤x_i≤100000，0≤y_i≤100000。
对于100%的数据，保证一定有解。
可以发现，不管oier与computer的对应顺序如何，结果相同。
code:
var i,j,n:longint;
x1,x2,y1,y2:int64;
a,b:int64;
begin readln(n);
x1:=0; y1:=0;
x2:=0; y2:=0;
for i:=1 to n do
begin readln(a,b);
x1:=x1+a;
y1:=y1+b;
end;
for i:=1 to n do
begin readln(a,b);
x2:=x2+a;
y2:=y2+b;
end;
writeln(abs(x2-x1)+abs(y1-y2));
end.
2，
题目描述 Description
OI教练BG在n天中每天早晨会给wxjlzbcd发一套题，其中包含A_i道题目。如果不做的话，题目会累加到下一天。
wxjlzbcd每天能够刷掉的题目数量为B_i，BG的题目数量太少，可能不能满足wxjlzbcd每天刷题的需求，如果题目数量不够，wxjlzbcd当天就不会刷题，因为空出来的时间他有可能会浪费掉。
但是wxjlzbcd不想天天颓废，他想知道自己最多能有多少天有题刷。
输入输出格式 Input/output输入格式：
输入第1行为一个整数n，表示天数。
第2行包括n个数字A_i，表示BG n天中每天发的题目数A_i。
第3行包括n个数字B_i，表示wxjlzbcd n天中每天能刷掉的题目数B_i。
输出格式：
输出第1行为一个整数ans，表示天数。
输入输出样例 Sample input/output样例测试点#1
输入样例：
5
1 4 1 2 3
1 2 3 4 5
输出样例：
4
说明 description对于40%的数据，保证1≤n≤1000；
对于100%的数据，保证1≤n≤250000，0≤a_i≤10^9，0≤b_i≤10^9。
神奇的贪心：
如果能刷题的话就刷；否则就判断以前的每天中有没有需要题数比当前大的，然后还原，取当前的。
用堆维护。。。。。。。。
code：
var n,left,day,total:int64;
i:longint;
num:array[1..250000] of int64;
demand:array[1..250000] of int64;
heap:array[1..250000] of int64;
procedure go_up(st,j:longint);
var i,temp:longint;
begin while (j div 2)>=st do
begin i:=j>>1;
if demand[heap[j]]>demand[heap[i]]
then begin emp:=heap[i];
heap[i]:=heap[j];
heap[j]:=temp;
j:=i;
end
else break;
end;
end;
procedure go_down(i,ed:longint);
var j,temp:longint;
begin
while (i<<1)<=ed do
begin
j:=i<<1;
if demand[heap[j+1]]>demand[heap[j]] then j:=j+1;
if demand[heap[j]]>demand[heap[i]]
then
begin
temp:=heap[i];
heap[i]:=heap[j];
heap[j]:=temp;
i:=j;
end
else
break;
end;
end;
begin readln(n);
for i:=1 to n do
read(num[i]);
readln;
for i:=1 to n do
read(demand[i]);
left:=0;
day:=0;
total:=0;
for i:=1 to n do
begin if left+num[i]>=demand[i]
then begin inc(day);
left:=left+num[i]-demand[i];
inc(total);
heap[total]:=i;
go_up(1,total);
end
else begin if demand[heap[1]]>=demand[i]
then begin left:=left+num[i]+demand[heap[1]]-demand[i];
heap[1]:=i;
go_down(1,total);
end
else left:=left+num[i];
end;
end;
write(day);
end.
3，
题目描述 Description
给出n个正整数，Archon、wxjlzbcd两个人轮流取任意数量的数，游戏的结束条件是n个数都被取走。
每次取数时，获得的得分为所取数中的最小值。
假设Archon先取数，Archon和wxjlzbcd的策略都是尽可能使得自己的得分减去对手的得分更大，请求出游戏结束时Archon的得分减去wxjlzbcd的得分为多少。
每次取数时，获得的得分为所取数中的最小值。
假设Archon先取数，Archon和wxjlzbcd的策略都是尽可能使得自己的得分减去对手的得分更大，请求出游戏结束时Archon的得分减去wxjlzbcd的得分为多少。
输入输出格式 Input/output
输入格式：
输入第1行为一个整数n，表示整数个数。
输入第2行为给出的n个整数a_i。
输出格式：
输出第1行为一个整数ans，表示Archon的得分减去wxjlzbcd的得分。
输入第1行为一个整数n，表示整数个数。
输入第2行为给出的n个整数a_i。
输出格式：
输出第1行为一个整数ans，表示Archon的得分减去wxjlzbcd的得分。
输入输出样例 Sample input/output
输入样例：
3
3
1 3 1
输出样例：
2
2
说明 description对于样例，Archon取走第二个数，wxjlzbcd取走第一个和第三个数。答案为3-1=2。
对于30%的数据，1≤n≤10；
对于100%的数据，1≤n≤1000000，1≤a_i≤10^9。
设f[i]为剩最小的i个数时前手与后手的最大差值
此时，假设前手取了j个数{0<=j<=i-1}
前手的增加得分：init[j]
后手的增加得分：f[j-1];
f[i]:=max{init[j]-f[j-1]} (0<=j<=i-1)
f[0]:=1;
要先qsort
{在最外层时，不要用head<=tail
而是head<tail
}
因为1≤n≤1000000,则要在每一次求值时不断更新。{prevent TLE}
code:
var n:longint;
i,j,k:longint;
f,init:array[0..1000000]of longint;
max:longint;
procedure qsort(x,y:longint);
var head,tail,k,temp:longint;
begin head:=x; tail:=y;
k:=init[(head+tail) div 2];
while head<tail do
begin while init[head]<k do inc(head);
while k<init[tail] do dec(tail);
if head<=tail
then begin temp:=init[head];
init[head]:=init[tail];
init[tail]:=temp;
inc(head);
dec(tail);
end;
end;
if head<y then qsort(head,y);
if x<tail then qsort(x,tail);
end;
begin readln(n);
for i:=1 to n do
read(init[i]);
qsort(1,n);
f[0]:=0;
max:=init[1]-f[0];
for i:=1 to n-1 do
begin f[i]:=max;
if max<init[i+1]-f[i]
then max:=init[i+1]-f[i];
end;
f[n]:=max;
writeln(f[n]);
end.
