题解 | #24点运算#
24点运算
http://www.nowcoder.com/practice/7e124483271e4c979a82eb2956544f9d
题目有点问题
对于一个用例 K Q 6 K 明明有解为K-Q/6+K 但是给出的答案是输出 NONE
代码如下,应该是没问题的,没有什么更好的精妙解法了,差不多是直接暴力的,但是因为总共的选择有限,所以程序运行起来还是很快
#include<bits/stdc++.h> using namespace std; map<int,string> revmap; void coutX(int a,int b,int c,int d,char op1,char op2,char op3){ string s; vector<int> tt{a,b,c,d}; vector<char> opp{op1,op2,op3}; for(int i=0;i<4;i++){ int x=tt[i]; if(x>=2&&x<=9){ s=s+to_string(x); }else{ s=s+revmap[x]; } if(i<3){ s=s+opp[i]; } } cout<<s<<endl; } int count(int left,int right,char op){ if(op=='*'){ return left*right; }else if(op=='/'){ return left/right; }else if(op=='+'){ return left+right; }else if(op=='-')return left-right; cout<<"出错!"<<endl; return 0; } bool twentyFour(int a,int b,int c,int d){ //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<endl; int aa=a,bb=b,cc=c,dd=d; vector<char> operatorT={'+','-','*','/'}; for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ for(int k=0;k<4;k++){ a=aa,b=bb,c=cc,d=dd;//需要每次都初始化。。。。 char op1=operatorT[i]; char op2=operatorT[j]; char op3=operatorT[k]; if(i>=2){//第一个运算符为* / 优先级比较高 a=count(a,b,op1); if(j>=2||k<2){ a=count(a,c,op2); a=count(a,d,op3); if(a==24){ coutX(aa,bb,cc,dd,op1,op2,op3); return true; } }else{ if(k>=2){ c=count(c,d,op3); a=count(a,c,op2); if(a==24){ coutX(aa,bb,cc,dd,op1,op2,op3); return true; } } } }else{//第一个不为* / if(j>=2){ b=count(b,c,op2); if(k>=2){ b=count(b,d,op3); a=count(a,b,op1); if(a==24){ coutX(aa,bb,cc,dd,op1,op2,op3); return true; } }else{ //cout<<b<<" "; a=count(a,b,op1); //cout<<a<<" "; a=count(a,d,op3); //cout<<a<<" "; if(a==24){ //cout<<aa<<op1<<bb<<op2<<cc<<op3<<dd<<endl; coutX(aa,bb,cc,dd,op1,op2,op3); return true; } } }else{ if(k>=2){ c=count(c,d,op3); a=count(a,b,op1); a=count(a,c,op2); if(a==24){ coutX(aa,bb,cc,dd,op1,op2,op3); return true; } }else{ a=count(a,b,op1); a=count(a,c,op2); a=count(a,d,op3); if(a==24){ coutX(aa,bb,cc,dd,op1,op2,op3); return true; } } } } } } } return false; } int main(){ vector<string> s(4); map<string,int> mp; mp.insert(pair<string,int>("10",10)); mp.insert(pair<string,int>("A",1)); mp.insert(pair<string,int>("J",11)); mp.insert(pair<string,int>("Q",12)); mp.insert(pair<string,int>("K",13)); revmap.insert(pair<int,string>(10,"10")); revmap.insert(pair<int,string>(1,"A")); revmap.insert(pair<int,string>(11,"J")); revmap.insert(pair<int,string>(12,"Q")); revmap.insert(pair<int,string>(13,"K")); while(cin>>s[0]>>s[1]>>s[2]>>s[3]){ if(s[0].size()>2||s[1].size()>2||s[2].size()>2||s[3].size()>2){ cout<<"ERROR"<<endl; continue; } vector<int> model(4); for(int i=0;i<4;i++) if(s[i][0]>='2'&&s[i][0]<='9'){ model[i]=stoi(s[i]); //cout<<model[i]<<" "; }else{ model[i]=mp[s[i]]; //cout<<model[i]<<" "; } //接下来也许是一个四重循环来排列元素 /*for(auto x:model){ cout<<x<<" "; }*/ //cout<<endl; bool fin=false; for(int i=0;i<4;i++){ if(fin)break; for(int j=0;j<4;j++){ if(fin)break; for(int k=0;k<4;k++){ if(fin)break; for(int l=0;l<4;l++){ if(fin)break; if(i!=j&&i!=k&&i!=l&&j!=k&&j!=l&&k!=l){//每个元素各取一次 //cout<<i<<j<<k<<l<<endl; int a=model[i],b=model[j],c=model[k],d=model[l]; //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<endl; if(twentyFour(a,b,c,d)){ fin=true; } } } } } } if(!fin)//找不到时的输出 cout<<"NONE"<<endl; } return 0; }