题意
题目链接 https://www.luogu.org/problemnew/show/P4064
Sol
这题就是一个很显然的贪心...
首先二分一个答案, 然后 check 是否可行. check 的时候我们需要对每个位置 \(i\), 维护出所有左端点在 \(i\) 左侧, 右端点在 \(i\) 右侧的所有区间. 最优策略一定是加右端点最远的.
然后就做完了, 复杂度 \(O(nlogn)\)
- #include<bits/stdc++.h>
- #define Fin(x) freopen(#x".in", "r", stdin);
- #define LL long long
- #define int long long
- using namespace std;
- const int MAXN = 1e5 + 10;
- const LL INF = 1e18;
- inline int read() {
- char c = getchar(); int x = 0, f = 1;
- while(c <'0' || c> '9') {if(c == '-') f = -1; c = getchar();}
- while(c>= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
- return x * f;
- }
- int N, M, K, A;
- vector<int> v[MAXN];
- LL a[MAXN], b[MAXN];
- bool check(int mid) {
- memset(b, 0, sizeof(b));
- priority_queue<int> q;
- int tag = 0, num = 0;
- for(int i = 1; i <= N; i++) {
- for(auto &x : v[i]) q.push(x);
- while(!q.empty() && q.top() <i) q.pop();
- tag += b[i];
- int now = a[i] + tag;
- while(now < mid && !q.empty() && q.top()>= i) {
- b[q.top() + 1] -= A; tag += A; q.pop();
- now += A; num++;
- }
- if(now <mid || num> K) return 0;
- }
- if(num <= K) return 1;
- }
- void solve() {
- N = read(); M = read(); K = read(); A = read();
- for(int i = 1; i <= N; i++) a[i] = read(), v[i].clear();
- while(M--) {
- int l = read(), r = read();
- v[l].push_back(r);
- }
- int l = 0, r = INF, ans = -1;
- while(l <= r) {
- int mid = l + r>> 1;
- if(check(mid)) l = mid + 1, ans = mid;
- else r = mid - 1;
- }
- cout << ans << '\n';
- }
- signed main() {
- for(int T = read(); T--; solve());
- return 0;
- }
- /*
- */
来源: http://www.bubuko.com/infodetail-2969394.html