As you may know, balloons are handed out during ACM contests to teams as they solve problems. However, this sometimes presents logistical challenges. In particular, one contest hosting site maintains two rooms, A and B, each containing a supply of balloons. There are N teams attending the contest at that site, each sitting at a different location. Some are closer to room A, others are closer to room B, and others are equally distant. Given the number of balloons needed by each team and the distance from each team to room A, and to room B, what is the minimum total possible distance that must be traveled by all balloons as they are delivered to their respective teams, assuming they are allocated in an optimal fashion from rooms A and B? For the purposes of this problem, assume that all of the balloons are identical. Input There will be several test cases in the input. Each test case will begin with a line with three integers: N A B Where N is the number of teams (1 ≤ N ≤ 1, 000), and A and B are the number of balloons in rooms A and B, respectively (0 ≤ A, B ≤ 10, 000). On each of the next N lines there will be three integers, representing information for each team: K DA DB Where K is the total number of balloons that this team will need, DA is the distance of this team from room A, and DB is this team’s distance from room B (0 ≤ DA, DB ≤ 1, 000). You may assume that there are enough balloons — that is, ∑(K′ s) ≤ A + B. The input will end with a line with three ‘0’s. Output For each test case, output a single integer, representing the minimum total distance that must be traveled to deliver all of the balloons. Count only the outbound trip, from room A or room B to the team. Don’t count the distance that a runner must travel to return to room A or room B. Print each integer on its own line with no spaces. Do not print any blank lines between answers. Sample Input 3 15 35 10 20 10 10 10 30 10 40 10 0 0 0 Sample Output 300
题意：每个要a[i]个气球，可以从A或B中拿，最小距离和首先肯定贪心地想离靠的近的。那这个时候肯定会有近的却不够的现象产生。那么就要考虑让怎么样位置的点去跑较远的。首先最好的情况就是都走最近的一边。现在从这里面挑出一些走另外一边，那走另外一边的挑出来后我想要答案贴近原来的最优情况，就使得每次挑出来增加的距离最小——也就是说abs（disL-disR）最小。 那么问题解决，排个序，优先让abs（disL-disR）大的先就近选择，免得损失大。剩下来考后的就算近的不够也只是多跑一点路（相比之前的）。
AC代码：
#include<iostream> #include<string> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include <queue> #include<sstream> #include <stack> #include <set> #include <bitset> #include<vector> #define FAST ios::sync_with_stdio(false) #define abs(a) ((a)>=0?(a):-(a)) #define sz(x) ((int)(x).size()) #define all(x) (x).begin(),(x).end() #define mem(a,b) memset(a,b,sizeof(a)) #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define rep(i,a,n) for(int i=a;i<=n;++i) #define per(i,n,a) for(int i=n;i>=a;--i) #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; typedef long long ll; typedef pair<ll,ll> PII; const int maxn = 1e6+200; const int inf=0x3f3f3f3f; const double eps = 1e-7; const double pi=acos(-1.0); const int mod = 1e9+7; inline int lowbit(int x){return x&(-x);} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d); inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;} inline ll inv(ll x,ll p){return qpow(x,p-2,p);} inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;} inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'|ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0', ch = getchar();return x*f; } int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} }; typedef struct Dis { ll num; ll L; ll R; ll d; }D; D a[maxn]; bool cmp(D a, D b) { return a.d > b.d; } int main() { ll n, A, B; while(cin>>n>>A>>B&&(n||A||B) ) { ll t = 0; rep(i,1,n) { ll l, r, m; m = read(); l = read(); r = read(); rep(j,1,m) { a[t].L = l; a[t].R = r; a[t].d = abs(l-r); t ++; } } sort(a,a+t,cmp); ll ans = 0; rep(i,0,t-1) { if(a[i].L <= a[i]. R) { if(A>0) { ans += a[i].L; A -= 1; } else ans += a[i].R, B -= 1; } else { if(B>0) { ans += a[i].R; B -= 1; } else ans += a[i].L, A -= 1 ; } } cout<<ans<<endl; } return 0; }