学步园

题目链接：http://www.topcoder.com/stat?c=problem_statement&pm=10342

题目大意：给定两个数x和y，通过对x和y某些位交换后，使得x*y的结果最大，交换次数给定

解题思路：因为x和y对应位不管怎么交换，x+y的值保持不变，所以要使x*y最大，只要是x和y之间的距离最小就可以。如何寻找最小距离的x和y呢？首先假设x>y，从左到右扫描，找到第一个x[i]<y[i]，使他们交换过来，继续扫描，后面的每位都保证x[i]<y[i]，并记录下交换的次数n和是否有某位相同的情况。如果n=swaps，则即为最大的；如果n<swaps,还得继续，如果有某位相同，则剩下的交换都交换这里就可以，如果没有相同的位，则判断剩下的交换次数是否是偶数，如果是，则通过对某个对应位，反复交换，不改变x和y，如果不是，只要把最后一个改变的位交换过来就可以；如果n>swaps，从数位较小的开始，对已经改变的变回去，操作n-swaps就可以。由于变与不变是相对的，所以通过计算两次，(x,y)和(y,x)，并去最大的那个结果。注意最大的结果不是字符串较大的那个。

#include <string><br /> #include <vector><br /> #include <iostream><br /> using namespace std;<br /> struct DigitsSwap<br /> {<br /> void swap(char &x,char &y)<br /> {<br /> char temp=x;x=y;y=temp;<br /> }<br /> string mult(string x,string y)<br /> {<br /> int n=x.size();<br /> vector<int> temp(n+n);<br /> //memset(temp,0,sizeof(temp));<br /> for(int i=0;i<n;i++)<br /> for (int j=0;j<n;j++)<br /> {<br /> temp[i+j]+=(x[i]-'0')*(y[j]-'0');<br /> }<br /> string an;<br /> //for(int k=0;k<2*(n-1);k++)<br /> //cout<<temp[k];<br /> //cout<<endl;<br /> for (int k=2*(n-1);k>0;k--)<br /> {<br /> temp[k-1]+=temp[k]/10;<br /> temp[k]%=10;<br /> an.push_back(temp[k]+'0');<br /> }<br /> while (temp[0]>0)<br /> {<br /> an.push_back(temp[0]%10+'0');<br /> temp[0]/=10;<br /> }<br /> reverse(an.begin(),an.end());<br /> return an;<br /> }<br /> string function(string x,string y,int swaps)<br /> {<br /> int n=x.size();<br /> int n1=0;<br /> bool flag=false;<br /> int i;<br /> bool f[55];<br /> memset(f,false,sizeof(f));</p> <p> //keep x>y<br /> for (i = 0;i < n;i++)<br /> {<br /> if (x[i]>y[i])<br /> {<br /> break;<br /> }<br /> else if(x[i]<y[i])<br /> {<br /> swap(x[i],y[i]);<br /> n1++;<br /> f[i]=true;<br /> break;<br /> }<br /> else<br /> {<br /> flag=true;<br /> }<br /> }<br /> //keep the diff of x and y smallest<br /> for (i++;i < n;i++)<br /> {<br /> if (x[i] > y[i])<br /> {<br /> swap(x[i],y[i]);<br /> n1++;<br /> f[i]=true;<br /> }<br /> else if (x[i] == y[i] && flag == false)<br /> {<br /> flag=true;<br /> }<br /> }<br /> //adjust according the swaps and n1<br /> if (n1 < swaps)<br /> {<br /> if (flag==false&&(swaps-n1)%2!=0)<br /> {<br /> swap(x[n-1],y[n-1]);<br /> }</p> <p> }<br /> else if (n1 > swaps)<br /> {<br /> int count=0;<br /> for (i=n-1;i>=0&&count<n1-swaps;i--) //count后没有等号<br /> {<br /> if(f[i]==true)<br /> {<br /> swap(x[i],y[i]);<br /> count++;<br /> }<br /> }<br /> }<br /> string temp=mult(x,y);<br /> //cout<<temp<<endl;<br /> return temp;<br /> }<br /> string maximalProduct(string x,string y,int swaps)<br /> {<br /> string ans1=function(x,y,swaps);<br /> string ans2=function(y,x,swaps);<br /> //返回较大的，注意不是直接字符串比较<br /> if(ans1.size()>ans2.size())<br /> return ans1;<br /> else if(ans1.size()<ans2.size())<br /> return ans2;<br /> else<br /> {<br /> for(int i=0;i<ans1.size();i++)<br /> if(ans1[i]>ans2[i]) return ans1;<br /> else if(ans1[i]<ans2[i]) return ans2;<br /> return ans1;<br /> }<br /> }<br /> };<br /> int main()<br /> {<br /> string x,y;<br /> int s;<br /> DigitsSwap temp;<br /> while(1)<br /> {<br /> cin>>x;<br /> cin>>y;<br /> cin>>s;<br /> cout<<temp.maximalProduct(x,y,s)<<endl;<br /> }<br /> }