3-21百度C++实习生笔试

有选择题，多选，编程。我没准备草稿纸，结果选择题有构造二叉树啥的，挺尴尬，靠想象做，多选有点难搞，我总觉得只有一个正确答案，因为没有草稿纸很多瞎选的，二十分钟选择题做完开始搞编程题。

编程题三道全通过，第一道题牛牛有n个食物每个食物能量是a[i]，牛牛至少吃掉m能量的食物会有饱腹感，问至少吃掉几个食物会有饱腹感，输出第一行是至少几个，第二行是应该吃的几个食物的编号，答案不唯一，输出一组即可，若全吃完都不饱就输出-1。简单题，把a数组从大到小排序然后顺序吃，但答案要求输出食物编号，所以排序前要先保留编号，我是设计了一个结构体。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

struct Node{
  int index, val;  
}a[1010];
int n, m;
bool cmp(const Node& x, const Node& y){
    return x.val > y.val;
}
int main()
{
    int T; cin >> T;
    while (T--){
        cin >> n >> m;
        for (int i = 0; i < n; ++i){
            cin >> a[i].val;
            a[i].index = i;
        }
        sort(a, a+n, cmp);
        int now = 0;
        int flag = -1;
        for (int i = 0; i < n; ++i){
            now += a[i].val;
            if (now >= m){
                flag = i;
                break;
            }
        }
        if (flag == -1) cout << -1 << endl;
        else {
            vector<int> tmp;
            for (int i = 0; i <= flag; ++i)
               tmp.push_back(a[i].index+1);
            cout << flag + 1 << endl;
            sort(tmp.begin(), tmp.end());
            cout << tmp[0];
            for (int i = 1; i <= flag; ++i) cout << " " << tmp[i];
            cout << endl;
        }
    }
    return 0;
}

/*
input
2
4 10
1 2 9 5
2 3
1 10
9

output
2
1 3
-1
*/

第二题牛牛有n个朋友喜欢演戏，他们对戏份的要求是a[i]，现在有m场戏，每场戏的戏份是b[j]，朋友i愿意演的戏需要满足a[i]>=b[j]，问保证尽可能多的人有戏可演的情况下每个朋友可以分配的戏的编号，分配不到的朋友就输出-1。也是排序，两个数组都从小到大排序，先给对戏份要求低的朋友分戏，如果当前b[j] < a[i]则j++，就是一个贪心的思路，因为最后要输出戏的编号所以也需要先保存编号，我的做法和第一题类似。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

struct Node{
    int index, val;
}a[1010], b[1010];
int n, m;
bool cmp(const Node& x, const Node& y){
    return x.val < y.val;
}
int main()
{
    int T; cin >> T;
    while (T--){
        cin >> n >> m;
        for (int i = 0; i < n; ++i){
            cin >> a[i].val;
            a[i].index = i;
        }
        for (int j = 0; j < m; ++j){
            cin >> b[j].val;
            b[j].index = j;
        }
        sort(a, a+n, cmp);
        sort(b, b+m, cmp);
        vector<int> ans(n, -1);
        int j = 0;
        for (int i = 0; i < n; ++i){
            while (j < m && b[j].val < a[i].val) ++j;
            if (j < m){
                ans[a[i].index] = b[j].index+1;
                ++j;
            }
            
        }
        cout << ans[0];
        for (int i = 1; i < n; ++i) cout << " " << ans[i];
        cout << endl;
    }
    return 0;
}

/*
input
1
3 6
33 66 99
3 6 9 30 60 90
output
5 6 -1
*/

第三题经典动态规划跳台阶，n阶台阶，每次最多跳m阶，要求每次跟前两次跳的阶数不同，问方案数。三维dp数组，dp[i][p][k]表示当前在台阶i处，一步跳了p阶，前一步跳了k阶，则dp[i][p][k] = 求和dp[i-p][k][j]。

#include<iostream>
#include<cstring>
using namespace std;
const long long mod = 1e9+7;

int n, m;
long long dp[100010][8][8];
int main()
{
    while (cin >> n >> m){
        memset(dp, 0, sizeof dp);
        for (int i = 0; i <= m; ++i) dp[i][i][0] = 1;
        dp[3][1][2] = dp[3][2][1] = 1;
        for (int i = 4; i <= n; ++i){
            for (int j = 0; j <= min(m, i); ++j){
                for (int k = 1; k <= min(m, i); ++k) if (k != j){
                    for (int p = 1; p <= min(i, m); ++p) if (p != j && p != k){
                        dp[i][p][k] = (dp[i][p][k] + dp[i-p][k][j]) % mod;
                    }
                } 
             }
        }
        long long ans = 0;
		for (int i = 1; i <= m; i++)
			for (int j = 0; j <= m; ++j)
				if (i != j)
					ans = (ans + dp[n][i][j]) % mod;
		cout << ans << endl;
    }
	return 0;
}

/*
input
7 3
output
2
*/

#百度##笔经#