程序员进阶之算法练习（四十二）
正文
题目一
题目链接 题目大意： n个学生参加测试，一共有m道题，每道题的答案可能是(A, B, C, D , E)中的一个； m道题分别有?1,?2,…,??，共m个分数； 现在已知道n个学生对m道题目的选择，假如题目的正确答案可以任意选择，想知道所有学生最大的分数总和是多少？
输入： 第一行? and ? (1≤?,?≤1000) 接下来n行，每行有m个字符，每个字符是 (A, B, C, D or E)表示选择的答案； 接下来一行，有m个整数，?1,?2,…,?? (1≤??≤1000)
输出： 最大的分数。
Examples input 2 4 ABCD ABCE 1 2 3 4 output 16
样例解释：答案是ABCD时，分数最大，最大值是16
题目解析： 每道题是相对独立的，可以分来开看； 对于每一道题，选择答案人数最多的结果，乘以分数即可得到这道题的最大分数； 累加每一道题得到 最大分数和。
int n, m;
cin >> n >> m;
string str[1001];
for (int i = 0; i < n; ++i) {
cin >> str[i];
}
int a[1001], ans = 0;
for (int i = 0; i < m; ++i) {
cin >> a[i];
int v[5] = {0}, cnt = 0;
for (int j = 0; j < n; ++j) {
v[str[j][i] - 'A']++;
cnt = max(cnt, v[str[j][i] - 'A']);
}
ans += cnt * a[i];
}
cout << ans << endl;题目二
题目链接 题目大意： 有n个数字，有一个操作：选择两个数字a[i]和a[j]（i ≠ j)，使得a[i]=a[i]-1，a[j]=a[j]-1; 现在想知道，能否执行若干次操作，使得所有的数字变为0.
输入： 第一行，整数? (2≤?≤10e5) 第二行，n个整数?1,?2,…,?? (1≤??≤10e9)
输出： 如果可以，输出YES； 如果不可以，输出NO；
Examples input 4 1 1 2 2 output YES input 6 1 2 3 4 5 6 output NO
题目解析： 这里的核心逻辑是如何分配这些数字。 先从小范围数据来分析，假如n=2，那么没得选只能a[0]，a[1]操作； 假如n=3，我们先把数组从小到大排序，有a[0]<a[1]<a[2]； 容易知道，如果a[0]+a[1]<a[2]的话，是无解的； 同时如果a[0]+a[1]+a[2]=sum，sum%2==1的话，也是无解的； 在其他情况下，有a[0]+a[1]>=a[2]，并且(a[0]+a[1]-a[2])%2==0； 那么，可以对a[0],a[1]进行操作，则相当于(a[0]+a[1]) -= 2，最终可以得到a[0]+a[1]=a[2]；
当n=4的时候，同样先排序，得到a[0]<a[1]<a[2]<a[3]； 为了复用上面的思考过程，我们可以把a[0],a[1]合并成一个数字来看，这个数字除了可以和其他数字进行-1操作，也可以自己和自己进行-1的操作； 再重复上面的思考过程，最终发现只有两种情况无解： 1、sum%2==1，和为奇数无解； 2、a[n-1]*2>sum，最大数超过和的一半，无解； 其他的情况，都可以用上面类似的方法得到一个解。
int n;
cin >> n;
lld sum = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
sum = sum + a[i];
}
sort(a, a + n);
if (sum % 2 || 2 * a[n - 1] > sum) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
}题目三
题目链接 题目大意： 有n个数字，?1,?2,…,??； 现在可以进行k次操作，每次可以选择一个数字a[i]，使得a[i]=a[i]+1； 问，进行k次操作，数组中的中位数最大为多少？
输入： 第一行，? and ? (1≤?≤2⋅1e5, ?是奇数, 1≤?≤1e9) 第二行，?1,?2,…,?? (1≤??≤1e9).
输出： 最大的中位数。
Examples input 3 2 1 3 5 output 5 input 5 5 1 2 1 1 1 output 3
题目解析： 题目的数据没有先后顺序相关，可以先对数据排个序，方便处理。 题目要求是中位数最大，假设我们的目标是s，那么从a[(n-1)/2]开始，所有的数字小于s的都要变大； 因为k值比较大，模拟的做法不可取。 考虑到在变大的过程中，我们每次都是固定处理后面n/2个数，那么如果s有解，则s-1也一定有解；（因为可以少变一些数字） 基于此线性特点，可以用二分来解决。
注意这里有个trick，二分的范围。
比如说这样的数据：
1 1000000000
1000000000另外就是二分的时候，要注意用int64来处理。
bool check(lld mid, lld n, lld k) {
for (lld i = (n - 1) / 2; i < n; ++i) {
if (a[i] < mid && k >= 0) {
k -= mid - a[i];
}
}
return k >= 0;
}
int main(int argc, const char * argv[]) {
// insert code here...
lld n, k;
cin >> n >> k;
for (lld i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a, a + n);
lld left = 1, right = a[n - 1] + k, ans = left;
while (left <= right) {
lld mid = (left + right) / 2;
if (check(mid, n, k)) {
ans = mid;
left = mid + 1;
}
else {
right = mid - 1;
}
}
cout << ans << endl;
return 0;
}题目四
题目链接 题目大意： 有一个n x m的网格，小明站在位置(1,1)； 现在小明每次可以选择移动一步：向上、向左、向右，但是不能向下，也不能超过网格； 网格中，只有某些特定的列可以往上走，这些列有q个（?1,?2,…,??） 某些格子放着宝藏，这些格子有k个，分别是??,??, (1≤??≤?, 1≤??≤?)
现在想知道，小明拿到所有的宝物，最少需要多少步；
输入： 第一行， ?, ?, ? and ? (2≤?,?,?,?≤2⋅1e5, ?≤?) 接下来k行，每行2个整数 ??,??, (1≤??≤?, 1≤??≤?) 最后一行有q个整数，?1,?2,…,?? (1≤??≤?)
输出： 最少移动步数。
Examples input 3 3 3 2 1 1 2 1 3 1 2 3 output 6 input 3 5 3 2 1 2 2 3 3 1 1 5 output 8 input 3 6 3 2 1 6 2 2 3 4 1 6 output 15
题目解析： 理清题目的要求和限制之后，我们可以知道： 1、我们要拿到所有的宝藏，就需要把每一层宝物都拿完才能选择上一层； 2、选择从哪一列上去是一个决策点； 3、假如在第i行时，初始位置是在第x列，计划选择第y列上去，则这一层的遍历最优解已经决定；
接下来简化这些问题，先看某一层的遍历宝藏问题，从贪心的角度来看，我们只有两个选择： 1、先走到最左边的宝藏，再走到最右边的宝藏； 2、先走到最右边的宝藏，再走到最左边的宝藏； 那么以这两个状态为节点，我们有dp[i][0]，dp[i][1]表示第i行，站在最左边和最右边的最小步数； 同时，我们需要把这一层的宝藏拿完，于是有dp[i][2],dp[i][3]表示第i行拿完宝藏后，站在最左边和最右边的最小步数；
容易知道，转移过程有两个： a.dp[i][0]，dp[i][1]可以由dp[i-1][2],dp[i-1][3]转移过来；（表示拿完宝藏上来） b.dp[i][2],dp[i][3]可以由dp[i][0]，dp[i][1]转移过来；（表示拿完这一层的宝藏）
情况b很简单，直接计算距离就可以得到转移方程； 情况a比较复杂，有两个转移初始点，同时有m个选择上来的地点，如果每个都遍历一遍，转移的时间代价太高； 为了简化这个过程，可以选出起点左右最近的两个点、终点左右最近的两个点，这样复杂度就从O(M)降为O(1)； 这个查找过程，可以用二分来解决。
注意事项: 错误1：第一行为空的情况，插入字符0； 错误2：某一行为空的情况，累计lastRow； 错误3：dp[i-1]改为lastRow; 错误4：long long； 错误5：binary search 的时候，传入的n，应该是q； 错误6：初始化错误，写成int的最大值，应该是longlong最大值；
写的时候没有专心，分了几次写，问题也多好几个；
typedef long long lld;
const lld N = 201000, M = 3010100, inf = 0x7fffffff;
const lld llinf = 0x7fffffff7fffffffll;
vector<lld> a[N];
lld dp[N][4];
lld b[N];
pair<lld, lld> binarySearch(lld val[], lld n, lld k) {
pair<lld, lld> pos;
lld left = 0, right = n; // [left, right) 左开右闭
pos.first = left;
while (left < right) {
lld mid = (left + right) / 2;
if (val[mid] == k) {
pos.first = mid;
break;
}
else if (val[mid] < k) {
pos.first = mid;
left = mid + 1;
}
else {
right = mid;
}
}
left = 0, right = n, pos.second = n - 1;
while (left < right) {
lld mid = (left + right) / 2;
if (val[mid] == k) {
pos.second = mid;
break;
}
else if (val[mid] < k) {
left = mid + 1;
}
else {
pos.second = mid;
right = mid;
}
}
return make_pair(val[pos.first], val[pos.second]);
}
lld cost(lld src, pair<lld, lld> pass, lld dest) {
return min(abs(src - pass.first) + abs(pass.first - dest), abs(src - pass.second) + abs(pass.second - dest));
}
int main(int argc, const char * argv[]) {
// insert code here...
lld n, m, k, q;
cin >> n >> m >> k >> q;
lld maxRow = 0;
for (lld i = 0; i < k; ++i) {
lld x, y;
cin >> x >> y;
--x;--y;
a[x].push_back(y);
maxRow = max(maxRow, x);
}
for (lld i = 0; i < q; ++i) {
cin >> b[i];
--b[i];
}
sort(b, b + q);
if (a[0].size() == 0) {
a[0].push_back(0); // 避免第一层没有宝藏的情况
}
for (lld i = 0; i < n; ++i) {
sort(a[i].begin(), a[i].end());
}
dp[0][0] = a[0].front();
dp[0][1] = a[0].back();
dp[0][2] = dp[0][1] + abs(a[0].back() - a[0].front());
dp[0][3] = dp[0][0] + abs(a[0].back() - a[0].front());
lld lastRow = 0;
for (lld i = 1; i < n; ++i) {
if (a[i].size()) {
// dp[i][0]最左边，可以从下一层的dp[i-1][2]最左边，dp[i-1][3]最右边转移过来
pair<lld, lld> posLeft = binarySearch(b, q, a[lastRow].front());
pair<lld, lld> posRight = binarySearch(b, q, a[lastRow].back());
dp[i][0] = llinf; // init
// 从下一层的最左边上来
dp[i][0] = min(dp[i][0], dp[lastRow][2] + (i-lastRow) + cost(a[lastRow].front(), posLeft, a[i].front()));
// 从下一层的最右边上来
dp[i][0] = min(dp[i][0], dp[lastRow][3] + (i-lastRow) + cost(a[lastRow].back(), posRight, a[i].front()));
dp[i][1] = llinf; // init
// 从下一层的最左边上来
dp[i][1] = min(dp[i][1], dp[lastRow][2] + (i-lastRow) + cost(a[lastRow].front(), posLeft, a[i].back()));
// 从下一层的最右边上来
dp[i][1] = min(dp[i][1], dp[lastRow][3] + (i-lastRow) + cost(a[lastRow].back(), posRight, a[i].back()));
dp[i][2] = dp[i][1] + abs(a[i].front() - a[i].back());
dp[i][3] = dp[i][0] + abs(a[i].front() - a[i].back());
lastRow = i;
}
}
cout << min(dp[maxRow][2], dp[maxRow][3]) << endl;
return 0;
}总结
四个题目均来自于 Codeforces Round #577 (Div. 2) 。 前三题偏思考，代码量比较小； 第四题的代码量看似比较多，其实就是动态规划+二分，只是代码写得比较拖沓：因为在尝试按照工程的思想去做题。 先做规划，想好方案，拆分模块，按部就班。
腾讯云开发者
