喵哈哈村与哗啦啦村的大战（三）
发布时间: 2017年3月27日 09:41 时间限制: 1000ms 内存限制: 128M
喵哈哈村因为和哗啦啦村争夺稀有的水晶资源，展开了激烈的战斗！
对于喵哈哈村而言，现在有n个战士，每个战士的能力值是a[i]，现在战士可以花费c[i]的代价使得自己的能力增加1点，或者降低1点。但是战士最终的能力值只能在l[i]与r[i]之间。
现在有个目标值s，你需要使得这n个战士的能力值之和为s才行。
问你是否可以，如果可以的话，请输出最小代价。
本题包含若干组测试数据。
第一行两个整数n，s；分别表示战士数量，战士能力值目标之和。
接下来n行，每行四个整数a[i],c[i],l[i],r[i]，描述如题所示。
满足1<=n<=50000,1<=S<=10000000,1<=l[i]<=a[i]<=r[i]<=1000,1<=c[i]<=1000
如果可行的话，输出最小代价。
否则输出impossible
复制
3 6 1 1 1 3 1 2 1 3 1 3 1 3
4
题解：这个题目就是贪心一下，贪心思想是：从最小的代价开始增加或者减少能力值。这里有个注意的地方，就是有几个情况，当前的能力值等于预期值；当前的能力值小于预期值；当前的能力值大于
预期值。分情况讨论一下就好！
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn=1e5+5; 5 struct node{ 6 int v, c, l, r; 7 }a[maxn]; 8 bool cmp(node a, node b){ 9 return a.c<b.c; 10 } 11 12 int main(){ 13 ll n, s; 14 while(cin>>n>>s){ 15 int now=0, cnt=0, f=1; 16 for(int i=0; i<n; i++){ 17 cin>>a[i].v>>a[i].c>>a[i].l>>a[i].r; 18 now+=a[i].v; 19 } 20 if(now==s) cout<<"0"<<endl; 21 else if(now<s){ 22 sort(a, a+n, cmp); 23 int j; 24 for(j=0; j<n; j++){ 25 if((s-now)<=(a[j].r-a[j].v)){ 26 cout<<cnt+(s-now)*a[j].c<<endl; 27 break; 28 }else{ 29 cnt=cnt+(a[j].r-a[j].v)*a[j].c; 30 now=now+(a[j].r-a[j].v); 31 } 32 } 33 if(j>=n) f=0; 34 }else if(now>s){ 35 sort(a, a+n, cmp); 36 int j; 37 for(j=0; j<n; j++){ 38 if((now-s)<=(a[j].v-a[j].l)){ 39 cout<<cnt+(now-s)*a[j].c<<endl; 40 break; 41 }else{ 42 cnt=cnt+(a[j].v-a[j].l)*a[j].c; 43 now=now-(a[j].v-a[j].l); 44 } 45 } 46 if(j>=n) f=0; 47 } 48 if(!f) cout<<"impossible"<<endl; 49 } 50 return 0; 51 }