地址:http://acm.uestc.edu.cn/#/problem/show/1557
题目:
Minimum C0st
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
There are NN numbers where the ithith is AiAi.
In order to make the sum of them changed to SS, you can make some numbers increased by one or decreased by one.
But you should spend CiCi dollars to increase or decreased AiAi by one, and the new AiAi should satisfies Li≤Ai≤RiLi≤Ai≤Ri.
Any number can be operated any times. What's the minimum cost to make the sum of all numbers changed to SS?
Input
The first line contains two integers N,SN,S,
Next NN lines each line contains four integers Ai,Ci,Li,RiAi,Ci,Li,Ri.
1≤N≤1000,1≤S≤106,1≤Ci≤1000,0≤Li≤Ai≤Ri≤10001≤N≤1000,1≤S≤106,1≤Ci≤1000,0≤Li≤Ai≤Ri≤1000
Output
If there is no solutions, print impossible
.
Otherwise, print one integer indicates the minimum cost to make the sum of all numbers changed to SS.
Sample input and output
Sample Input | Sample Output |
---|---|
3 6 |
4 |
Source
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std; struct nmb
{
int dat,cost,l,r;
}a[]; bool cmp(nmb a,nmb b)
{
return a.cost<b.cost;;
} int n,s,sum,ans,last; int main()
{
cin>>n>>s;
for(int i=;i<=n;i++)
{
scanf("%d%d%d%d",&a[i].dat,&a[i].cost,&a[i].l,&a[i].r);
sum+=a[i].dat;
}
sort(a+,a+n+,cmp);
sum-=s;
sum=-sum;
if(sum<)
{
for(int i=;i<=n;i++)
{
if(sum+a[i].dat-a[i].l>)
{
last=i;
break;
}
ans+=(a[i].dat-a[i].l)*a[i].cost;
sum+=a[i].dat-a[i].l;
}
ans-=sum*a[last].cost;
if(last!=)
sum=;
}
else if(sum>)
{
for(int i=;i<=n;i++)
{
if(sum+a[i].dat-a[i].r<)
{
last=i;
break;
}
ans+=(a[i].r-a[i].dat)*a[i].cost;
sum-=a[i].r-a[i].dat;
}
ans+=sum*a[last].cost;
if(last!=)
sum=;
}
if(sum!=)
{
cout<<"impossible"<<endl;
return ;
}
cout<<ans<<endl;
return ;
}