今日学习记录
1. 小红的数组操作2024 年第七届传智杯程序设计挑战赛初赛.G
关键词：二分答案
问题分析：
- 小红拿到了一个数组,她每次可以进行如下操作,使其减去 x,小红希望 kkk 次操作之后,该数组的最大值尽可能小.请你求出这个尽可能小的最大值.
核心思路
- 经典的优先队列,直接做很简单,狗都会做
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k,x;cin>>n>>k>>x;
priority_queue<int,vector<int>> pq;
while(n--){
int m;cin>>m;
pq.push(m);
}
while(k>0){
int p = pq.top();
pq.pop();
while(k>0&&p>=pq.top()) p -=x,k--;
pq.push(p);
}
cout<<pq.top();
return 0;
}但这可是 G 题啊,肯定没这么简单,看看题目给的数量级,k 最大可以到 1e9,就是说要操作 1e9 次,使用优先队列必然会超时,大大滴超时,只能过 1.11 分,说明题目刻意呢 2. 那么该怎么做呢,我们来模拟一下答案的反过程,比如,我先知道答案,那么就要把数组中所有的数都要减去 x,直到这个数小于答案,然后看减去的操作次数是否等于 k,大于 k,就说明答案小了,小于 k,说明答案大了,那么再想想答案的极端情况,可以发现答案的单调性,这样我可以直接使用二分答案来做,而且 check 函数比较好写 但是,你以为这就完了吗?这才刚刚开始,这道题难的是边界处理,我吃了 10 发 w 才试出边界,这个边界确实不好想,因为按道理来说他给出的值,a 最大值应该为 1e9 左右,而二分上下限就应该是搜索答案的范围,即上界就应该为 1e9 左右,但是这个题的上下界很难分辨,答案按道理来说是不可能为负数,但是搜索范围要搜到-1e18,你就说 n 不 nb 吧,而且上界要搜到 1e18,所以这个题的难点就在这里,可以一直试答案
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6+5;
ll n, k, x;
ll a[N];
bool check(ll target) {
ll operations = 0;
for (int i = 0;i<n;i++) {
if (a[i] > target) {
ll needed = (a[i] - target + x - 1) / x;
operations += needed;
if (operations > k) {
return false;
}
}
}
return true;
}
int main() {
cin >> n >> k >> x;
for (ll i = 0; i < n; i++) {
cin >> a[i];
}
ll left = -1e18;
ll right = 1e18;
ll ans = 0;
while (left <= right) {
ll mid = left + (right - left) / 2;
if (check(mid)) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
cout << ans << endl;
return 0;
}只能说尽量开大点边界,避免漏解
学到的点：
- 二分边界处理