程序员进阶之算法练习（四十三）
正文
题目1
题目链接
题目大意：
屏幕上有a*b个像素点，其中第（x、y）个像素点已经损坏；（x和y从0开始）
现在想在屏幕上选出一个矩形，这个矩形的边与屏幕的边缘平行，并且不包括损坏的像素点(x，y）；
问这个矩形的最大面积是多少？
输入：
第一行 整数𝑡 (1≤𝑡≤10^4)
接下来t行，每行4个整数 𝑎,𝑏,𝑥 and 𝑦 (1≤𝑎,𝑏≤104; 0≤𝑥<𝑎; 0≤𝑦<𝑏)
输出：
每个样例一行，每行一个整数，表示最大的面积数。
Examples
input
1
8 8 0 0
output
56
样例解释-最大的面积7*8=56
题目解析：
只有四种可能，损坏点的上下左右。
如下图，假设是损坏点在红色点，那么红色点上面、左边的两种情况必然如下。
再考虑损坏点右边、下面，选取最大值即可。
int t;
cin >> t;
while (t--) {
int n, m, x, y;
cin >> n >> m >> x >> y;
int ans = 0;
ans = max(ans, x * m);
ans = max(ans, (n-x-1) * m);
ans = max(ans, n * y);
ans = max(ans, n * (m-y-1));
cout << ans << endl;
}
题目2
题目链接
题目大意：
小明放学回家，要经过若干个公交车站；每个地方都有公共交通工具可以到达，如果是公交车，我们用A来表示；如果是地铁，我们用B来表示；
公交车的费用是a，之后连续的公交车站都可以免费到达；
地铁的费用是b，之后连续的地铁站都可以免费到达；
以AABBBAB为例，如果从第一个站开始，通过公共交通到达最后一个站，小明需要买三次票：
公交车1次，可以经过AA；
地铁1次，可以经过BBB；
公交车1次，可以经过A；（A下车之后就到达目的地B了，不需要买票）
现在小明身上之后p块钱，可能钱不够所有的交通费用，需要走路到某个站开始乘坐公共交通工具，小明想知道最少要走到哪一站？（从左到右）
输入：
第一行 整数𝑡 (1≤𝑡≤10^4)
接下来t个样例，每个样例两行
第一行3个整数 𝑎,𝑏,𝑝 (1≤𝑎,𝑏,𝑝≤10^5)
第二行n个字符
输出：
每个样例一行，每行一个整数k，表示最少要步行到第k个站。
Examples
input
5
2 2 1
BB
1 1 1
AB
3 2 8
AABBBBAABB
5 3 4
BBBBB
2 1 1
ABABAB
output
2
1
3
1
6
题目解析：
用逆推的方式，从最后一个站开始往前考虑。
从倒数第二个开始，假设小明当前持有的票是cur，根据cur=A或者cur=B，可以知道当前他是否需要买票；
然后倒着遍历，直到钱不够，得到正确答案。
考察的是实现的巧妙程度和边界处理。
int t;
cin >> t;
while (t--) {
int a, b, p;
cin >> a >> b >> p;
cin >> s;
char cur = 0;
int pos = (int)strlen(s) - 2;
while (pos >= 0) {
if (cur == s[pos]) {
--pos;
continue;
}
else {
int cost = s[pos] == 'A' ? a : b;
if (p >= cost) {
p -= cost;
cur = s[pos];
--pos;
continue;
}
else {
break;
}
}
}
cout << pos + 2 << endl;
}
题目3
题目链接
题目大意：
给出n个整数b[i]，现在希望构造一个数组，包括2n整数a[i]；
这个数组字典序尽可能的小，并且满足 𝑏[𝑖]=min(𝑎[2𝑖−1],𝑎[2𝑖])；
输入：
第一行 整数𝑡 (1≤𝑡≤10^4)
接下来t个样例，每个样例两行
第一行1个整数n， (1≤𝑛≤100).
第二行n个整数b[i] (1≤b[i]≤2𝑛）
输出：
每个样例一行，每行2n个整数；
Examples
input
5
1
1
2
4 1
3
4 1 3
4
2 3 4 5
5
1 5 7 2 8
output
1 2
-1
4 5 1 2 3 6
-1
1 3 5 6 7 9 2 4 8 10
题目解析：
从要求来看，就是最终的结果是2个就有1个原来的数字；
由于字典序要求最小，并且𝑏[𝑖]是min(𝑎[2𝑖−1],𝑎[2𝑖])，所以b[i]肯定是放在前面的位置；
整个构造的数组是b[0], x, b[1], x, b[2], x....
问题变成，如何在1~2n的数字中，找到合适的数字分配到x的位置中。
按照题目的要求，可以每次从1~2n中没出现的数字找到一个，然后分到x中；如果所有合法的数字都不存在，则题目无解。
考察的是构造能力。
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
memset(mp, 0, sizeof(int) * (n * 2 + 1));
for (int i = 0; i < n; ++i) {
cin >> a[i];
mp[a[i]] = 1;
}
int ok = 1;
vector<int> ans;
for (int i = 0; i < n; ++i) {
ans.push_back(a[i]);
int find = 0;
for (int j = a[i] + 1; j <= 2*n; ++j) {
if (!mp[j]) {
find = 1;
mp[j] = 1;
ans.push_back(j);
break;
}
}
if (!find) {
ok = 0;
break;
}
}
if (!ok) {
cout << -1 << endl;
}
else {
for (int i = 0; i < n*2; ++i) {
cout << ans[i] << " ";
}
cout << endl;
}
}
题目4
题目链接
题目大意：
有n个整数a[i]的数组，现在可以对数组的数字分别进行一个操作：
令某个数a[i]=a[i]+1，但是代价是t[i]；
现在希望数组中没有重复的数字，问最小的代价是多少？
输入：
第一行1个整数n， (1≤𝑛≤200000).
第二行n个整数𝑎[𝑖] (1≤𝑎[𝑖]≤10^9).
第二行n个整数𝑡[𝑖] (1≤𝑡[𝑖]≤10^5)；
输出：
一个整数m，代表最小的代价；
Examples
input
5
3 7 9 7 8
5 2 5 7 5
output
6
题目解析：
先考小数据的情况，当有两个数字相同时，我们会把代价最大的留着，代价小的数字+1；
当有3个数字相同时（假设都是x），我们我们会按照代价从大到小的分配x/x+1/x+2；
同理，当有若干个数字相同时，同样可以按照代价从大到小排序。
再回过来看题目的数据，我们从小到大来分析数据；
如果某个数字只有1个，则直接跳过；
如果某个数字出现2个以上，则最大代价的数字留着，其他的数字需要加一；
考虑到当数字x到数字y之间，会存在某些区间也可以分配数字，那么我们同样需要按照代价从大到小去分配；
每个数字只会分配一次，保持代价从大到小，可以使用优先队列，整体的复杂度是O(NLogN)，在题目可接受范围内。
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
scanf("%d", &node[i].first);
}
for (int i = 0; i < n; ++i) {
scanf("%d", &node[i].second);
}
sort(node, node + n, cmp);
priority_queue<Node> pq;
lld pos = 0, lastValue = 0;
lld ans = 0;
while (pos < n) {
lld val = node[pos].first;
// 在处理每组，第一个数字之前，先把之前能填补的数字补上
lld cnt = val - lastValue;
while (cnt > 0 && !pq.empty()) {
Node top = pq.top();
pq.pop();
ans += (lastValue - top.first) * top.second;
++lastValue;
--cnt;
}
// 把这一组的数字加上
while (pos < n && node[pos].first == val) {
pq.push(node[pos]);
++pos;
}
lastValue = val;
}
lastValue = node[n - 1].first;
while (!pq.empty()) {
Node top = pq.top();
pq.pop();
ans += (lastValue - top.first) * top.second;
++lastValue;
}
cout << ans << endl;
总结
题目1是分类讨论；
题目2思路直接，但是实现过程容易有边界问题；
题目3用优先队列，比较容易解决；
题目4也是贪心的思路，加上排序；
