程序员进阶之算法练习（五十三）
正文
题目1
题目链接
题目大意：
有三堆石头，分别有a、b、c个；
现在可以执行操作：
1、从第一堆拿出1个石头，第二堆拿出2个石头；
2、从第二堆拿出1个石头，第三堆拿出2个石头；
以上的操作，必须保证堆中有足够石头才允许操作。
问最多，可以从这三堆石头中拿出多少个。
输入：
第一行，是样例个数 𝑡 (1≤𝑡≤100)；
接下来t行表示t个样例，每个样例一行，每行有三个数字a、b、c (0≤𝑎,𝑏,𝑐≤100)；
输出：
每个样例一行，输出拿到的石头数量。
input
3
3 4 5
1 0 5
5 3 2
output
9
0
6
题目解析：
由题目的条件可以知道，操作1和操作2都会依赖第二堆的石头，所以第二堆石头的分配就成为了关键；
为了高效利用第二堆石头，我们优先执行操作2，再执行操作1。
int main(int argc, const char * argv[]) {
int a, b, c;
int t;
cin >> t;
while (t--) {
cin >> a >> b >> c;
int ans = min(c / 2, b);
cout << min((b - ans) / 2, a) * 3 + ans * 3 << endl;
}
return 0;
}
题目 2
题目链接
题目大意：
给出两个整数l和r，已知l <= r；
现在希望找到一个整数x，要求是 l<=x<=r，并且x中没有相同的数字；
如果能找到则输出这个数字；
如果不能找到则输出-1；
输入：
两个整数l和r； (1≤𝑙≤𝑟≤1e5)
输出：
输出整数x；如果不存在则输出-1；
题目解析：
直接遍历整数区间的数字，判断每个数字是否合法。
扩展思考题🤔：假如题目的数据范围非常大，甚至没有限制呢？在无法枚举的情况下，求出一个最小的解。
int main(int argc, const char * argv[]) {
int x, y;
cin >> x >> y;
while (x <= y) {
int ok = 1;
int a[10] = {0};
int tmp = x;
while (tmp) {
if (a[tmp % 10]) ok = 0;
a[tmp%10] = 1;
tmp /= 10;
}
if (ok) {
cout << x << endl;
return 0;
}
++x;
}
cout << -1 << endl;
return 0;
}
题目3
题目链接
题目大意：
有n个整数，𝑎1,𝑎2,…,𝑎𝑛；
可以去掉中间某一段连续的数字，要求剩下的数字没有重复。
问，最少需要去掉多少个数字。
输入：
第一行，整数𝑛 (1≤𝑛≤2000)
第二行，n个整数𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9)
输出：
最少需要去掉数字个数
Examples
input
3
1 2 3
output
0
input
4
1 1 2 2
output
2
题目解析：
不考虑复杂度，直接枚举去掉区间的坐标[l, r]，有n^2的可能；
判断剩下数字有没有重复需要O(N)的时间，总的时间复杂度是O^3，超过了可接受范围；
假如去掉x个数字有解，则去掉x+1个数字也有解，可以用2分来优化；
这样复杂度可以优化为O(NNlogN)，可接受范围内。
提交错误（TLE）1次，数字较大且map耗时较多；改为scanf，添加hash处理，可以满足要求。
map<int, int> h;
for (int i = 0; i < n; ++i) {
int t;
scanf("%d", &t);
if (!h[t]) {
h[t] = ++cnt;
}
a[i] = h[t];
}
int left = 0, right = n; // [left, right)
int ans = n - 1;
while (left < right) {
int mid = (left + right) / 2;
int ok = 0;
for (int k = 0; k < n; ++k) { //
if (check(n, k, k + mid)) {
ok = 1;
break;
}
}
if (ok) {
ans = mid;
right = mid;
}
else {
left = mid + 1;
}
}
cout << ans << endl;
更优化的做法：
假设去掉的数字区间是[l, r]，那么剩下的就是[0, l-1]和[r+1, n-1]的区间。
容易知道[0, l-1]和[r+1, n-1]里面是没有重复元素的。
从0开始遍历，可以很容易得到以0为起点的不重复元素区间；
同理，从n-1开始向左遍历，可以得到以n-1为结束的不重复元素区间；
以上两步的处理都是O(N)复杂度。
假设得到左边最大的不重复元素区间，也得到右边最大不重复元素区间；
那么就可以枚举左边区间长度（从长度为0开始），对于[0, k)的区间，求出[0, k)中所有元素的最右边距离difMax，那么从difMax+1开始，右边的元素就不会再和左边的[0, k)相同，这样再和右边最大不重复元素区间取一个较小值。
可以O(N)解决这个问题。
提交错误（WA）1次，少考虑了左边完全不需要的情况，ans的初始化有误，比如说：
8
1 1 1 1 5 6 7 1
这样的样例会返回7，因为默认了第一个1数字会选择，实际上还有一种情况是左边数字1区间不取。
int a[N];
int vis[N];
int cnt = 0;
// [l, r)
bool check(int n, int l, int r) {
memset(vis, 0, sizeof(vis));
for (int i = 0; i < l; ++i) {
if (!vis[a[i]]) {
vis[a[i]] = 1;
}
else {
return false;
}
}
for (int i = r; i < n; ++i) {
if (!vis[a[i]]) {
vis[a[i]] = 1;
}
else {
return false;
}
}
return true;
}
int main(int argc, const char * argv[]) {
// insert code here...
int n;
cin >> n;
map<int, int> leftMap, rightMap, gapMap;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
gapMap[a[i]] = i;
}
int leftDifMax = 0, rightDifMax = 0;
for (int i = 0; i < n; ++i) {
if (leftMap[a[i]]) {
break;
}
leftMap[a[i]] = 1;
leftDifMax = i;
}
for (int i = n - 1; i >= 0; --i) {
if (rightMap[a[i]]) {
break;
}
rightMap[a[i]] = 1;
rightDifMax = i;
}
int tmp = 0, ans = (n - rightDifMax);
for (int i = 0; i <= leftDifMax; ++i) {
tmp = max(tmp, gapMap[a[i]]);
int r = max(rightDifMax, tmp + 1);
ans = max(ans, i + 1 + (n - r));
}
cout << (n - ans) << endl;
return 0;
}
题目4
题目链接
题目大意：
给出n个数字，每次可以选择若干个数字，将他们进行平均；（如果不能整除，会用分数来表示）
这个操作的次数不限制；
问最终最多有多少个数字可以大于x？
输入：
第一行，整数𝑡表示有t个样例数量 (1≤𝑡≤1000)
每个样例第一行， 整数𝑛 and 𝑥 (1≤𝑛≤10^5, 1≤𝑥≤10^9)
接下来一行n个整数𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤10^9)
输出：
每个样例一行，最终大于数字x的数量；
Examples
input
4
4 3
5 1 2 1
4 10
11 9 11 9
2 5
4 3
3 7
9 4 9
output
2
4
0
3
题目解析：
把数字从大到小排序，从数字大的开始选择：
1、如果该数字大于x，直接入选；
2、如果该数字小于x，并且加进来不会导致sum/count 小于x，则加进来；
直到数字不能选择，则得到最多的数字。
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
lld n, x;
cin >> n >> x;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
sort(a, a + n);
lld sum = 0, ans = 0;
for (int i = n - 1; i >= 0; --i) {
if (sum + a[i] >= x * (ans + 1)) {
sum += a[i];
++ans;
}
else {
break;
}
}
cout << ans << endl;
}
return 0;
}
题目5
题目链接
题目大意：
小明在打游戏，有n只怪物围绕成一圈，第1只和第n只相邻；
第i只怪物的血量为a[i]，小明每次可以攻击一只怪物，使得怪物的血量-1；
当怪物的血量小于等于0的时候会死亡，并且产生爆炸，对第i+1个位置的怪物造成b[i]点伤害；（如果是第n只怪物爆炸，则是对第1只怪物造出伤害）
现在想知道，小明最少攻击多少次，才能使得所有怪物都爆炸；
输入：
第一行，整数𝑡表示有t个样例数量 (1≤𝑡≤1000)
每个样例第一行， 整数𝑛 (2≤𝑛≤300000)
接下来n行，每行两个整数𝑎𝑖 and 𝑏𝑖 (1≤𝑎𝑖,𝑏𝑖≤1e12)
输出：
每个样例一行，小明的最少攻击次数。
Examples
input
1
3
7 15
2 14
5 3
output
6
题目解析：
题目有两个点使得决策比较复杂：1、n个怪物绕成一个圈；2、怪物死亡之后，会产生爆炸；
先不考虑怪物死亡后爆炸的问题，就是n只怪物的血量和；
再考虑爆炸的情况，由于题目要求的是最终所有怪物都死亡，即所有怪物都会爆炸，那么可以直接减去爆炸影响的血量；
接下来的问题是，找到n个怪物中，应该首先攻击哪一个，使得其最先爆炸；
这个可以先统计一遍所有怪物减去被爆炸影响后的血量和，然后遍历每一个怪物，枚举这个怪物如果最先爆炸，最终的攻击次数。
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
scanf("%lld%lld", &a[i], &val[i]);
}
lld sum = max(0ll, a[0] - val[n - 1]);
for (int i = 1; i < n; ++i) {
sum = sum + max(0ll, a[i] - val[i - 1]);
}
lld ans = sum - max(0ll, a[0] - val[n - 1]) + a[0]; // 直接打死第0个
for (int i = 1; i < n; ++i) {
lld tmp = sum - max(0ll, a[i] - val[i - 1]) + a[i];
ans = min(ans, tmp);
}
cout << ans << endl;
}
return 0;
}
思考🤔：
如果是双向爆炸呢？
即位置i有多种可能爆炸顺序， i最先爆炸，i-1先爆炸然后i爆炸，i+1先爆炸然后i爆炸，i-1和i+1都爆炸然后i再爆炸；
这样需要考虑复杂很多！
总结
题目1 简单贪心，因为两个操作的控制要素不多，比较容易抉择；
题目2 简单模拟，题目的要求和范围都很简单，但是扩展题目的需要一点思路+代码能力；
题目3 暴力计算，枚举区间的做法比较暴力，收获也比较少，优化做法会更佳；
题目4 排序选择，排序简化思考，核心把平均数用和表达出来；
题目5 简化思考，部分决策因素会导致题目很复杂，从结果反推，配合枚举是很好的方式。
