milk.cpp

USACO chapter one.May hope it useful to someone

/*
ID: chenkai4
PROG: milk
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("milk.in");
ofstream out("milk.out");
#define MAXARRAY 10000

int N,M;
int P[5001],tA[5001];

//---------QuickSort-----------
//Use:快排,非递归
//O(n*logn)
#define PUSH(A,B) {sl[sp]=A;sr[sp]=B;sp++;}
#define POP(A,B) {sp--;A=sl[sp];B=sr[sp];}
void Quicksort(int l,int r)
{
	static int sl[MAXARRAY], sr[MAXARRAY], sp;
	int i,j,p,t;
	sp=0;
	PUSH(l,r);
	while(sp)
	{
		POP(l,r);
		i=l;j=r;p=P[(i+j)/2];
		while(i<=j)
		{
			
			while(P[i]<p)i++;while(P[j]>p)j--;
			if(i<=j)
			{
				t=P[i];P[i]=P[j];P[j]=t;
				t=tA[i];tA[i]=tA[j];tA[j]=t;
				i++;j--;
			} 
		}
		if(l<j)PUSH(l,j);
		if(i<r)PUSH(i,r);
	}
}

//-------End QuickSort---------

int main()
{
	in>>N>>M;
	for(int a=1;a<=M;a++)
		in>>P[a]>>tA[a];
	Quicksort(1,M);int nc=1,cost=0;
	while(N)
	{
		if(N>=tA[nc])
		{
			N-=tA[nc];
			cost += P[nc]*tA[nc];
		}
		else
		{
			cost += P[nc]*N;
			N=0;
		}
		nc++;
	}
	out<<cost<<endl;
	return 0;
}