1535.cpp

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

#include<iostream>
#include<string>
#include<cmath>
#include<fstream>
using namespace std;
int num1(string s){
   int res=0;
   for(int i=0;i<s.length()/2;i++)
	   res+=(s[i]-'0');
   return res;
}
int num2(string s){
   int res=0;
   for(int i=s.length()/2;i<s.length();i++)
	   res+=(s[i]-'0');
   return res;
}
long small(string s,int n1,int n2){
   int cha=n1-n2,now=s.length()-1;
   long res=0,e=1;
   while(cha>0){
	   while(s[now]=='9') {now-=1;e*=10;}
	   s[now]=char(s[now]+1);
	   res+=e;
	   cha-=1;
   }
   return res;
}
void deal(string & s,int now,int & f){
   s[now]='0';
   s[now-1]=char(s[now-1]+1);
   for(int i=s.length()-1;i>=s.length()/2+1;i--)
	   if(s[i]>'9'){
           s[i]=char(s[i]-10);
		   s[i-1]=char(s[i-1]+1);
	   }
   if(s[s.length()/2]>'9') f=1;
   else f=0;
}
void predeal(string & s){
   s[s.length()/2-1]=char(s[s.length()/2-1]+1);
   for(int i=s.length()/2-1;i>0;i--)
	   if(s[i]>'9'){
           s[i]=char(s[i]-10);
		   s[i-1]=char(s[i-1]+1);
	   }
}
long turn(string s){
    predeal(s);
	long res=0,e=1;
	for(int i=s.length()-1;i>=s.length()/2;i--){
        res+=(s[i]-'0')*e;
		s[i]='0';
		e*=10;
	}
	res=e-res;
	return res+small(s,num1(s),num2(s));
}
long big(string s,int n1,int n2){
   string copy=s;
   long temp=0,e=1;
   int cha=n2-n1,now=s.length()-1,stop=s.length()/2,f;
   while(now!=stop){
      cha-=((s[now]-'0')-1);
	  temp+=('9'-s[now]+1)*e;
	  deal(s,now,f);
	  if(f) return turn(copy);
	  else{
		 if(cha==0) return temp;
		 else if(cha<0) return temp+small(s,num1(s),num2(s));
		 now-=1;
		 e*=10;
	  }
   }
   return turn(copy);
}
int main(){
   //ifstream cin("1535.txt");
   string input;
   int n1,n2;
   while(cin>>input){
       n1=num1(input);n2=num2(input);
	   if(n1==n2) cout<<"0"<<endl; 
       if(n1>n2)  cout<<small(input,n1,n2)<<endl;
	   if(n1<n2)  cout<<big(input,n1,n2)<<endl;
   }
   return 0;
}