1444.cpp

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

#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
using namespace std;
class item{
public:
	string name;
	int totals,penal;
	vector<int> penalvec;
	item(string s,int n){name=s;totals=penal=0;penalvec.resize(n,0);}
};
int binarySearch(vector<item> & data,string value){
 int low=0;
 int high=data.size();
 while(low<high){
   int mid=(low+high)/2;
   if(data[mid].name==value) return mid;
   else if(data[mid].name<value)
        low=mid+1;
   else high=mid;
 }
 return low;
}
int cmp(const item & a,const item & b){
 if(a.totals!=b.totals) return a.totals>b.totals;
 else if(a.penal!=b.penal) return a.penal<b.penal;
 else return a.name<b.name;
}
int main(){
	ifstream cin("in.txt");
    int n,i,j,t;
	cin>>n;
	string name,status;
	vector<item> vec;
    while(cin>>t>>name>>i>>status){
       j=binarySearch(vec,name);
	   if(j==vec.size()||vec[j].name!=name){
             vec.insert(vec.begin()+j,item(name,n));
	   }
	   if(status=="AC"){
		   if(vec[j].penalvec[i-1]!=-1){
              vec[j].penalvec[i-1]+=t;
			  vec[j].totals+=1;
			  vec[j].penal+=vec[j].penalvec[i-1];
			  vec[j].penalvec[i-1]=-1;
		   }
	   }
	   else{
           if(vec[j].penalvec[i-1]!=-1){
              vec[j].penalvec[i-1]+=20; 
		   }
	   }
	}
	sort(vec.begin(),vec.end(),cmp);
	t=0;int lasts=100000000,lastp=-10000000;
	for(i=0;i<vec.size();i++){
	   if(vec[i].totals==0) break;
	   if(vec[i].totals!=lasts||vec[i].penal!=lastp){
           cout<<setiosflags(ios::left)<<setw(10)<<++t<<setw(30)<<vec[i].name<<setw(10)<<vec[i].totals<<vec[i].penal<<endl;
		   lasts=vec[i].totals; lastp=vec[i].penal;
	   }
	   else{
           cout<<setiosflags(ios::left)<<setw(10)<<"          "<<setw(30)<<vec[i].name<<setw(10)<<vec[i].totals<<vec[i].penal<<endl;
	   }
	}
}