洛谷P4064 [JXOI2017]加法(贪心 差分)
程序员文章站
2022-03-25 18:56:33
题意 "题目链接" Sol 这题就是一个很显然的贪心。。。 首先二分一个答案,然后check是否可行。check的时候我们需要对每个位置$i$,维护出所有左端点在$i$左侧,右端点在$i$右侧的所有区间。最优策略一定是加右端点最远的。 然后就做完了, 复杂度$O(nlogn)$ cpp includ ......
题意
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; } /* */