【题外话】
感谢UBUNTU为保存程序做出贡献：https://paste.ubuntu.com ；
感谢洛谷OJ的私人题库保存题面：https://www.luogu.org ；
现在我的题解的所有程序均保存在UBUNTU上，需要时单击超链接查看 ；
由于题目的不确定性，现在所有测试数据的建立全部来自于参加本次巨石杯的选手
OYCY & LSH 下面的程序为本人程序，暂且未知评测状态，会有误差，会及时更正！！！
5月14日 绿城育华NOIP巨石杯试卷解析
T1 最大的最小
【地址】https://www.luogu.org/problem/show?pid=U8888
【题面】
给出k组数据(x,y)表示有x个y在一个数列中，现在需要你在这个数列当中，把这些数两两配对，每两个配对的数的和设为sum，我们取最大的sum记为Maxsum，请输出Maxsum的最小值，正所谓“最大的最小”。
输入格式：第1行一个数k，表示有k组数，接下来k行每行两个数x,y表示在数列中有x个y
输出格式：1行1个数表示Maxsum的最小值
样例#1
输入
4
1 1
3 4
2 2
2 3
输出 6
范围：x,y,k<=100,000
【样例解释】
对于样例我们可以制造出这么一个序列：14442233
可以发现，对于该序列进行所谓的配对有6!种可能，在这6!种排法中可以发现这样配对可以求出Maxsum 的最小值：
14 24 24 33 得出的最小值为6，没有另外一种方法比它更优了
【解析】
对于样例我们可以发现纯暴力时间为O(0.5(x的总和)!)
远远超过时间限制，而且不能实现!
于是想到最优解的贪心求法!
简单分析样例我们发现，上述的样例解释是基于这样一个数列的：12233444，
发现该数列是数列14442233的排序结果，所以我们第一个想到的是对数列快排！
对于本题，暴力法求解是最容易想到的方法！
但是如果用到qsort的话，暴力法的时间复杂度是O(k*x*y*log(k*x*y))，
100%超过时间限制TLE，于是暴力法无法AC。
于是，对于读入数据不能暴力存储，怎么办，结构体存储!
定义： rec=record x,n:longint; end;
这里的x表示数x，n表示数x有n个；
对于数x进行快排，同时交换整个结构体；这样求出了一个有序的数列。
由于可能有重复的数x，所以需要去重，而qsort后x相同的几个数一定是连续的。
所以再用2层while(时间复杂度趋于线性)去重即可。
这样就得出了rec类型的数组a，从头尾两端逐步逼近：由于对于一样的头尾的值，得出的总和一样，所以不必要进行冗余计算
取头尾指针指向的两个数的个数求最小值，即为接下来有几个一样的和数！
如果某一个数为0，那么就下一个。同时找出所谓的Maxsum即可。
until 头尾指针相交；
主要程序段：
while i<=k do begin
lasti:=i; sum:=ta[i].n;
while (ta[i].x=ta[i+1].x)and(i<=k) do begin
inc(i); sum:=sum+ta[i].n; end;
inc(p); a[p].x:=ta[lasti].x; a[p].n:=sum;
inc(i);
end;//排序后去重
i:=1; j:=p;
maxsum:=-maxlongint;
while i<j do begin
step:=min(a[i].n,a[j].n);
sum:=a[i].x+a[j].x;
dec(a[i].n,step); dec(a[j].n,step);
if a[i].n=0 then begin inc(i); end;
if a[j].n=0 then begin dec(j); end;
if maxsum<sum then maxsum:=sum;
end;//贪心求解
对于这个贪心，我们需要有理论上的严格证明，为什么排序过后就是所求的数列？
证明：“不排序的数列不是所求最优的数列”如下：
以第一和最后一个之和为例，如果，第一个不与最后一个取和，那么第一个数势必和除最后一个数的数取和，那么得出的数势必比原来的数字要小，由于整个数列的和一定，那么对于这个Maxsum来说势必受到这个和的小而大，所以得出的Maxsum太大不是所求最优的解，所以命题“不排序的数列不是所求最优的数列”成立，贪心正确！
【程序】https://paste.ubuntu.com/24585852/
type rec=record
x,n:longint;
end;
var k,i,j,p,lasti,maxsum,sum,step:longint;
ta,a:array[-..]of rec;
function min(a,b:longint):longint;
begin
if a>b then exit(b)
else exit(a);
end;
function max(a,b:longint):longint;
begin
if a<b then exit(b)
else exit(a);
end;
procedure qsort(l,r:longint);
var i,j,mid:longint;
t:rec;
begin
i:=l; j:=r;
mid:=ta[(l+r)div ].x;
while i<j do
begin
while ta[i].x<mid do inc(i);
while ta[j].x>mid do dec(j);
if i<=j then begin
t:=ta[i]; ta[i]:=ta[j]; ta[j]:=t;
inc(i);dec(j);
end;
end;
if l<j then qsort(l,j);
if r>i then qsort(i,r);
end;
begin
readln(k);
for i:= to k do readln(ta[i].n,ta[i].x);
qsort(,k);
i:=; p:=;
while i<=k do begin
lasti:=i; sum:=ta[i].n;
while (ta[i].x=ta[i+].x)and(i<=k) do begin
inc(i); sum:=sum+ta[i].n; end;
inc(p); a[p].x:=ta[lasti].x; a[p].n:=sum;
inc(i);
end;
i:=; j:=p;
maxsum:=-maxlongint;
while i<j do begin
step:=min(a[i].n,a[j].n);
sum:=a[i].x+a[j].x;
dec(a[i].n,step); dec(a[j].n,step);
if a[i].n= then begin inc(i); end;
if a[j].n= then begin dec(j); end;
if maxsum<sum then maxsum:=sum;
end;
writeln(maxsum);
end.
T2 愤怒的小鸟
【地址】https://www.luogu.org/problem/show?pid=U9243
【题面】
有一数轴上有n只猪，坐标分别为X1 、X2、X3……Xn，现在玩家有k只炸弹鸟，撞到地面就会发生爆炸。每一只小鸟的能量都是w，落到点P（点表示的数）后会使P±w的范围内的猪收到伤害，求最小的能量的值w
输入格式
第1行有2个数n,k 表示有n只猪，用户有k只鸟（可以不全用完）
第2行有n个数表示每只猪的坐标（不保证有序）
输出格式
1行，表示最小的能量值w
输入
5 3
-1 1 2 6 9
输出
2
范围
对于100%的数据
x[i]<=100,000,000
n,k<=100,000
【解析】
首先看到数据范围x[i]<=100,000,000，范围如此之大想到不能用暴力法求解。那么非常奇怪，这么大的数据范围用什么办法可以通过呢？一开始想用贪心但是好像毫无线索。
画个图仔细分析，对于样例，你可以在下方建立一个数轴。
-1 1 2 6 9 画上一个点，表示这是一个猪。
看看在能量值为1时且所用的mink<=3是否可行？答案是不能！
能量值++，为2时，能否保证所用mink<=3？答案是可以你可以把2个猪放在坐标为2和7处就可以炸死所有的猪！
这样看来这么大的程序，又有坐标，不由的让人想到二分答案算法（准确的说是思想）
好了，事实上本题的标解就是二分答案，笔者也是看了数据范围后枉然想到二分答案的!
总结下二分答案的思想：以求最小值的最大值（最小值最大化）为例，尝试一个可能的答案，如果这个答案符合题目条件，那么它肯定是“最小”（可行解），但不一定是“最大”（最优解），然后我们换个更大的可能答案，如果也符合条件，那这个新可行解就更优，不断重复即可。
二分答案的前提：
1.答案区间上下限确定，即最终答案在哪个范围是容易知道的。
2.检验某值是否可行。
3.可行解满足区间单调性，即若x是可行解，则在答案区间内x+1（或是x-1）可能也可行。
解释一下什么是区间单调性：函数的单调性（monotonicity）也可以叫做函数的增减性。当函数 f(x) 的自变量在其定义区间内增大（或减小）时，函数值f(x)也随着增大（或减小），则称该函数为在该区间上具有单调性。
非常形象的解释！这样我们可以得出二分答案的基本格式：
while l<=r do begin
mid:=(l+r)div 2;
if pd(mid)=true then r:=mid-1 else l:=mid+1; end;
注意这里l和r在while循环开始时要赋值为区间的开始和结束区间结点。
而pd是一个function（pascal中叫函数，有返回值，返回值为boolean类型，表示能不能取）
是自我根据题目的意义来写，一般来说是用到贪心的知识来解答，所以二分答案和贪心一般是在一起的！
本题的重点不在这里，在于下面这个贪心，笔者寻求证明许久终于找到了拙劣的证明方法。首先我们来探讨一下pd函数的作用。
其实略略思考，二分答案的主体是什么？是能量值，所以pd传入的值为能量值w所以pd函数作用是判断在能量值为w的情况下最少投掷的鸟的个数并和k做比，若小于等于k则成立，大于k则不成立！
贪心的重点是判断在能量值为w的情况下最少投掷的鸟的个数！
考虑到两点之间在鸟威力为w的情况下让鸟的爆炸范围覆盖整个区间（不浪费）的情况一定是落点为两只猪的正中间，这样，对猪的坐标排序后，这个落点p为x+[(x+y)/2]，爆炸范围是p±w，如果相邻两只猪是可以被一个鸟所摧毁的，那么判断第三只猪依次列推。而如果相邻两只猪不可以被一个鸟所摧毁，即两只猪会被2只鸟摧毁，那么依次拓展，由于前方所用的鸟的只数是最优的，所以一定会多1只鸟即两只相邻的猪中的前面一个猪，不管怎么样都需要一只额外的鸟来摧毁。这种算法是两重while循环嵌套可以完成的！
回过头看，这道题是不是符合用二分答案求解的三个前提？我们依次论证。
1、 答案区间上下限确定，即最终答案在哪个范围是容易知道的。
其实非常简单，炸弹的爆炸威力一定在0到相差最大的两只鸟的距离的一半的范围内，用数学语言来叙述就是（假设x1-xn排序完成）令l=1；r=(xn-x1)/2
能量的范围在区间[l,r]或者是(l-1,r+1)
2、 .检验某值是否可行。
上述贪心很好的证明这点，我们只要通过一个简单的贪心就可以判断是不是符合题目要求。
3、 可行解满足区间单调性。
首先区间我们人为的将其具有单调性（排序），而数据本身w范围也具有单调性，大就是大，小就是小（我们要求越小越好）
从中可以发现，本题完全可以用二分答案来解决，有关二分答案的具体内容在此不再赘述，希望通过这一题的解答来抛砖引玉。
【程序】
var a:array[..]of int64;
n,k,i,mid,l,r:longint;
function pd(w:int64):boolean;
var i,mink,lasti:longint;
p:int64;
begin
i:=; mink:=;
while i<=n do begin
inc(mink);
lasti:=i;
p:=(a[i+]+a[i])div ;
while (p+w>=a[i+])and(p-w<=a[i])and(i<=n) do begin
inc(i);
if i=n then break;
p:=(a[lasti]+a[i+])div ;
end;
inc(i);
end;
if mink>k then exit(false)
else exit(true);
end;
procedure qsort(l,r:longint);
var t,i,j,mid:longint;
begin
i:=l; j:=r;
mid:=a[(l+r)div ];
while i<j do
begin
while a[i]<mid do inc(i);
while a[j]>mid do dec(j);
if i<=j then begin
t:=a[i]; a[i]:=a[j]; a[j]:=t;
inc(i);dec(j);
end;
end;
if l<j then qsort(l,j);
if r>i then qsort(i,r);
end;
begin
readln(n,k);
for i:= to n do read(a[i]);
qsort(,n);
l:=; r:=a[n]-a[];
while l<r do begin
mid:=(l+r)div ;
if pd(mid)=true then r:=mid else l:=mid+;
end;
writeln(l);
end.
T3 武林高手
【地址】https://www.luogu.org/problem/show?pid=U9308
【题面】
有B个帮派的高手功力可能不同，现在高手们约架，占据了n个据点，每个据点可能有多个高手，发功时，发功点的据点承受高手的原始功力，其他据点从左到右承受的功力依次递减。每个据点所承受的总功力等于所有高手对此据点造成的功力值之和
现在知道据点个数为n，帮派个数B与每个帮派高手的功力值，以及这些高手同时发功时各个据点所承受的功力，求至少有几个高手在发功
输入格式
第1行两个数，据点数n和帮派数B
第2行描述每个帮派，共计B个数表示该帮派的高手的功力值为V[i]
第3行描述n个数表示每个据点最后承受的功力值W[i]
输出格式 1行表示至少有几个高手在发功
输入输出样例
输入
5 2
5 7
0 17 16 20 19
输出 4
范围：对于100%的数据满足：
0<v[i]<=100,000
0<B<=100
n<=1,000,000
【解析】
这道题目其实是很难考虑的！
暴力bfs dfs可以骗分但是不是最优解，最优解为dp+模拟。
时间复杂度为O(max(w[i])*B)，显然100,000*100=10,000,000不超时
建立递推式f[i] 表示在累积功力值增加i时的最少人数。
[问题]思考：f[i-v[j]]+1可以表示为什么？
好了，想得出来的看答案，想不出来了我们看下面的一段举例。
对于样例，
f[i-5]+1表示在增加能力值累积为i时从i-5 时最少人数增加一个功力值为5的高手
f[i-7]+1表示在增加能力值累积为i时从i-7 时最少人数增加一个功力值为7的高手
看到这里，你可能会恍然大悟！
[答案] f[i-v[j]]+1可以表示为在增加能力值累积为i时从i-v[i]时的最少人数中多了一个功力值为v[i]的高手.
而f[i-v[i]]+1只可能从有限步中取最小值得来，这个有限的步数即为B
所以动态转移方程为f[i]=min(f[i],f[i-v[j]]+1);
然后再对w数组进行处理（模拟的部分）
备份w为tw； w[i]=0àw[i+1]=tw[i+1]; w[i]<>0àw[i+1]=tw[i+1]-tw[i]+1
扫一遍w累加f[w[i]]即可得ans，输出ans（累加值）
【程序】https://paste.ubuntu.com/24604486/
var i,j,ans,n,B,maxw:longint;
f:array[-..]of longint;
v,w,tw:array[..]of longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a)
else exit(b);
end;
begin
readln(n,B);
for i:= to B do read(v[i]);
for i:= to n do begin
read(w[i]);
if w[i]>maxw then maxw:=w[i];
end;
fillchar(f,sizeof(f),$7f-);
f[]:=;
for i:= to maxw do
for j:= to B do
f[i]:=min(f[i-v[j]]+,f[i]);
tw:=w;
for i:= to n- do begin
if tw[i]= then w[i+]:=tw[i+]
else w[i+]:=tw[i+]-tw[i]+;
end;
for i:= to n do begin
inc(ans,f[w[i]]);
end;
writeln(ans);
end.
杭州文澜中学 罗嘉诚
2017年5月28日