2 找角色
输入:
1
3 6
33 66 99
3 6 9 30 60 90
输出:
5 6 -1
输入:
1
3 6
66 33 99
3 6 9 30 60 90
输出:
6 5 -1
输入:
1
3 6
66 33 99
90 6 9 30 60 3
输出:
1 5 -1
#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
struct MyStruct
{
int mark;
int num;
};
bool cmp(MyStruct& t1, MyStruct& t2)
{
return t1.num < t2.num;
}
int main()
{
int T; cin >> T;
vector<MyStruct> vec1;
vector<MyStruct> vec2;
vector<MyStruct> res;
int n, m;
int tmp;
MyStruct t;
while (T--)
{
vec1.clear(); vec2.clear(); res.clear();
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> tmp;
t.mark = i;
t.num = tmp;
vec1.push_back(t);
}
sort(vec1.begin(), vec1.end(),cmp);
for (int i = 0; i < m; i++)
{
cin >> tmp;
t.mark = i;
t.num = tmp;
vec2.push_back(t);
}
sort(vec2.begin(), vec2.end(),cmp);
for (int i = 0, j = 0; i < n; i++)
{
if (j>=m)
{
t.mark = -1;
t.num = vec1[i].mark;
res.push_back(t); continue;
}
while(vec1[i].num>vec2[j].num)
{
j++;
}
t.mark = vec2[j++].mark+1;
t.num = vec1[i].mark;
res.push_back(t );
}
sort(res.begin(), res.end(), cmp);
for (int i = 0; i < n; i++)
{
cout << res[i].mark << " ";
}
cout << endl;
}
}
3 爬台阶
任意一步不能与前两步上升的台阶数相同。
输入:
7 3
输出:
2
输入:
7 4
输出:
10
"[]"内为下一步可选的台阶数,"[]"外为当前所选的台阶数
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200904133321211.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcxNTI4Nw==,size_16,color_FFFFFF,t_70#pic_center)
#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
void full_step(vector<int>& vec,int N)
{
for (int i = 0; i < N; i++)
{
vec.push_back(i + 1);
}
}
void backtrace(int&sum,int pre,int next, vector<int>& vec,int &N, int& M, int &res)
{
for (int i = 0; i < N; i++)
{
if (pre == vec[i] || next == vec[i])
{
continue;
}
sum += vec[i];
if (sum >= M)
{
if (sum == M)
{
res++;
}
sum -= vec[i];
return;
}
backtrace(sum, next, vec[i], vec, N, M, res);
sum -= vec[i];
}
}
int main()
{
int M, N; cin >> M >> N;
vector<int> vec;
full_step(vec,N);
int sum = 0;
int res = 0;
int pre = N+1, next= N + 1;
backtrace(sum, pre, next, vec, N, M, res);
cout << res << endl;
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)