原题： ZOJ 3676 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3676
题意：给每个朋友一瓶可乐，可乐有普通和高级两种，每个朋友只能喝一瓶可乐，喝普通可乐的朋友会给你P个瓶盖，喝高级可乐的朋友会给你Q个瓶盖。问最多能得到多少个瓶盖。瓶盖可以借。
解法：因为瓶盖可以借任意多个，所以按Q-P排序即可，二分临界点Q-P=0的点，即Q-P<m的让他和普通可乐，Q-P>m的喝高级可乐，Q-P=m的无所谓喝什么。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define N 100007 struct node
{
int P,Q;
int dif;
}p[N]; int SP[N],SQ[N]; int cmp(node ka,node kb)
{
return ka.dif < kb.dif;
} int main()
{
int n,m,k;
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
SP[] = SQ[] = ;
for(i=;i<=n;i++)
{
scanf("%d%d",&p[i].P,&p[i].Q);
p[i].dif = p[i].Q-p[i].P;
}
sort(p+,p+n+,cmp);
for(i=;i<=n;i++)
{
SP[i] = SP[i-]+p[i].P;
SQ[i] = SQ[i-]+p[i].Q;
}
for(i=;i<m;i++)
{
scanf("%d",&k);
int low = ;
int high = n;
int res = -;
while(low <= high)
{
int mid = (low+high)/;
if(p[mid].dif < k)
low = mid + ;
else
{
res = mid;
high = mid - ;
}
}
if(res == -) //如果全小于k，则全喝普通的
printf("%d\n",SP[n]);
else
printf("%d\n",SP[res-]+SQ[n]-SQ[res-]-(n-res+)*k);
}
}
return ;
}