1214.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<iostream>
#include<fstream>
#include<algorithm>
#include<string>
#include<vector>
#include<iomanip>
using namespace std;
class item{
public:
	int d,n;
	string s;
	item(int a,int b,string c){d=a;n=b;s=c;}
};
int cmp(const item & a,const item & b){
    if(a.s!=b.s) return a.s<b.s;
	else return a.d<b.d;
}
void output(vector<item> free){
    sort(free.begin(),free.end(),cmp);
	string s="";
	for(int i=0;i<free.size();i++){
		while(free[i].s.length()<30) free[i].s.insert(free[i].s.end(),' ');
		if(free[i].s==s) cout<<"                              "<<setiosflags(ios::right)<<setw(10)<<free[i].d<<setw(10)<<free[i].n<<endl;
        else{
		  cout<<free[i].s<<setiosflags(ios::right)<<setw(10)<<free[i].d<<setw(10)<<free[i].n<<endl;
          s=free[i].s;
		}
	}
}
int main(){
  //ifstream cin("in.txt");
  int i,j,k,l,d,n,m=0;
  string s;
  vector<item> pre,sold,free;
  cout<<"Problem 8 by team x\n";
  while(cin>>d&&d!=-1){
      if(m<d) m=d;
	  cin>>n;
      getline(cin,s);
	  s.erase(&s[0]);
	  //cout<<d<<" "<<n<<" "<<s<<endl;
      pre.push_back(item(d,n,s));
  }
  while(cin>>d){
      if(m<d) m=d;
	  cin>>n;
	  getline(cin,s);
	  s.erase(&s[0]);
	  //cout<<d<<" "<<n<<" "<<s<<endl;
      sold.push_back(item(d,n,s));
  }
  for(i=1;i<=m;i++){
	  cout<<"\nFrozen dishes at the end of day"<<setiosflags(ios::right)<<setw(4)<<i<<":\nDish                     Prepared on day  Quantity\n==================================================\n";
	  vector<item> daysold,daypre;
	  j=0;
	  while(j<pre.size()&&pre[j].d==i){
          daypre.push_back(pre[j]);
		  pre.erase(&pre[j]);
	  }
	  j=0;
	  while(j<sold.size()&&sold[j].d==i){
          daysold.push_back(sold[j]);
		  sold.erase(&sold[j]);
	  }
	  for(j=0;j<daysold.size();j++){
          for(k=0;k<daypre.size();k++)
			  if(daysold[j].s==daypre[k].s){
                  if(daysold[j].n>=daypre[k].n){//当天准备的不够，要去拿冰箱里的
                      daysold[j].n-=daypre[k].n;
					  daypre.erase(&daypre[k]);
					  {//去冰箱拿
						  for(l=0;l<free.size();l++){
                              if(daysold[j].n&&daysold[j].s==free[l].s){
                                  if(free[l].n<=daysold[j].n){
                                      daysold[j].n-=free[l].n;
									  free.erase(&free[l]);
									  l-=1;
								  }
								  else{
                                      free[l].n-=daysold[j].n;
						              daysold[j].n=0;
								  }
							  }
						  }
					  }
					  break;
				  }
				  else{//有的多，要放进冰箱
                      daypre[k].n-=daysold[j].n;
					  daysold[j].n=0;
					  //free.push_back(daypre[k]);
					  //daypre.erase(&daypre[k]);
					  break;
				  }
			  }
		  if(daysold[j].n)
			  for(l=0;l<free.size();l++){
                  if(daysold[j].n&&daysold[j].s==free[l].s){
                       if(free[l].n<=daysold[j].n){
                            daysold[j].n-=free[l].n;
							free.erase(&free[l]);
							l-=1;
						}
					   else{
                          free[l].n-=daysold[j].n;
						  daysold[j].n=0;
						  break;
					   }
				  }
			  }
		  
	  }
  	  for(l=0;l<daypre.size();l++)
          free.push_back(daypre[l]);
	  output(free);
  }//for i(day)
  cout<<"End of problem 8 by team x\n";
}