程序员进阶之算法练习（四十三）
正文
题目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也是贪心的思路，加上排序；
腾讯云开发者
