Home > Old Blog Posts > USACO 1.3.1 Mixing Milk

USACO 1.3.1 Mixing Milk


这应该是USACO第一道要用排序的题目

主要思想为贪心,排序后,每次选择当前最便宜的。

代码:

/*
ID: dementr1
PROG: milk
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“milk.in”);
ofstream fout(“milk.out”);
void swap(int *a, int *b)
{
int x=*a;
*a=*b;
*b=x;
}
int partition(int A[][2],int left, int right)
{
int i=(left+right)/2,j;
swap(&A[i][0],&A[right][0]);
swap(&A[i][1],&A[right][1]);
i=left-1;
for(j=left;j<right;j++)
{
if(A[j][0]<A[right][0])
{
i++;
swap(&A[i][0],&A[j][0]);
swap(&A[i][1],&A[j][1]);
}
}
i++;
swap(&A[i][0],&A[right][0]);
swap(&A[i][1],&A[right][1]);
return i;
}
void quicksort(int A[][2], int left, int right)
{
int i;
if(left<right)
{
i=partition(A,left,right);
quicksort(A,left,i-1);
quicksort(A,i+1,right);
}
}
int main()
{
int i,n,m,a[5000][2];
fin>>n>>m;
for(i=0;i<m;i++)
{
fin>>a[i][0]>>a[i][1];
}
quicksort(a,0,m-1);
int money=0;
i=0;
while(n>0)
{
if(a[i][1]>n)
{
money+=n*a[i][0];
break;
}
else
{
money+=a[i][1]*a[i][0];
n-=a[i][1];
i++;
}
}
fout<<money<<endl;
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: