程序员进阶之算法练习（五十三）
正文
题目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 简化思考，部分决策因素会导致题目很复杂，从结果反推，配合枚举是很好的方式。