顺丰科技2017笔试-小C负责设计一种新的益智数字游戏
目录
顺丰科技2017笔试 小C负责设计一种新的益智数字游戏
小C负责设计一种新的益智游戏。游戏分A、B两方，规则如下：
1.A方在一个纸片上写一个不超过6位的数值N，同时给出一个目标数M；
2.B方对写有数值N的纸片进行分割，分割成的每个纸片上有一个数，所有纸片上数的和不能大于目标数M，但需要尽可能与M接近。
3.若N与M相同，则不进行分割。
4.若无论如何分割，所得的碎纸片上数之和都大于目标数M，则表示错误。
5.若有多种不同的分割方式可以得到相同的最优结果。则拒绝分割。
游戏开发之前，小A计划先编写一个模拟程序。给定两个数，第一个是目标数M，第二个是写在纸片上的数N，输出分割的方式。
输入：
输入包括多组数据，每一组数据为一行，包括两个正整数M和N，保证两个数都不会以0开头，而且两个数最多只包含6个数字。
输入的最后一行包括由空格分隔两个0，表示输入的结束。
输出：
对每组输入数据，给出相应的输出。可能有三种不同的输出结果：
sum part1 part2 …
rejected
error
上述结果表示如下：
sum为碎纸片上数之和，即：sum = part1+part2+…。part j为碎纸片上数，顺序与待碎纸片上原始数中数字出现的次序一致。
若无论如何分割，所得碎纸片上数的和都大于目标数，则输出”error”。
若有多种不同的分割方式可得到相同的最优结果，则输出”rejected”。
样例输入
50 12346
376 144139
9274378 927438
18 3312
9 3142
25 1299
111 33333
103 862150
6 1104
0 0
样例输出
43 1 2 34 6
283 144 139
927438 927438
18 3 3 12
error
21 1 2 9 9
rejected
103 86 2 15 0
rejected
使用回溯法
代码如下：
#include <iostream>
#include <vector>
using namespace std;
vector<int> Split(int n)
{
vector<int> res;
while(n)
{
int tmp = n % 10;
res.insert(res.begin(),tmp);
n /= 10;
}
return res;
}
void Proc(int M, vector<int> &N, int index, vector<int> &split, int &max_sum, vector<int> &res,bool &isRejected)
{
if (index >= N.size())
{
int sum = 0;
for (int i=0; i<split.size(); i++)
sum += split[i];
if (sum > M) return;
if (sum < max_sum) return;
if (sum == max_sum)
{
isRejected = true;
return;
}
isRejected = false;
res.clear();
max_sum = sum;
for (int i=0; i<split.size(); i++)
res.push_back(split[i]);
return;
}
for (int l=1; l<=N.size()-index; l++)
{
int temp = 0;
for (int i=0; i<l; i++)
temp = temp * 10 + N[index+i];
split.push_back(temp);
Proc(M,N,index+l,split,max_sum,res,isRejected);
split.pop_back();
}
}
int main()
{
vector<int> M,N;
int m,n;
while (1)
{
cin>>m>>n;
if (m == 0 && n == 0) break;
M.push_back(m);
N.push_back(n);
}
for (int i=0; i<M.size(); i++)
{
vector<int> split = Split(N[i]);
vector<int> splitTemp;
vector<int> res;
int max_sum = 0;
bool isRejected = false;
Proc(M[i],split,0,splitTemp,max_sum,res,isRejected);
if (isRejected)
{
cout<<"rejected"<<endl;
}
else if (max_sum == 0)
{
cout<<"error"<<endl;
}
else
{
cout<<max_sum<<" ";
for (int j=0; j<res.size(); j++)
cout<<res[j]<<" ";
cout<<endl;
}
}
return 0;
}