USACO Mixing Milk
快排+贪心,还要注意0 0的情况。。
/*
ID: djgreen1
LANG: C
PROB: milk
*/
#include
long a[5000],p[5000];
void qsort(int l,int r)
{
int i,j,pivot;
long temp;
i=l;
j=r;
pivot=p[rand()%(r-l+1)+l];
while (i<j)
{
while (p[i]<pivot) i++;
while (p[j]>pivot) j--;
if (i<=j)
{
temp=p[i];
p[i]=p[j];
p[j]=temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
i++;
j--;
}
}
if (j>l) qsort(l,j);
if (i<r) qsort(i,r);
}
int main()
{
FILE *in=fopen("milk.in","r"),*out=fopen("milk.out","w");
long n,m,i,milk=0,price=0;
fscanf(in,"%d%d",&n;,&m;);
if (n==0)
{
fprintf(out,"0\n");
fclose(out);
return 0;
}
for(i=0;i<m;i++) fscanf(in,"%d%d",&p;[i],&a;[i]);
fclose(in);
srand(time(NULL));
qsort(0,m-1);
for(i=0;i<m;i++)
{
if (milk+a[i]<n)
{
milk+=a[i];
price+=p[i]*a[i];
}
else
{
price+=(n-milk)*p[i];
break;
}
}
fprintf(out,"%d\n",price);
fclose(out);
}
comments powered by Disqus