251208 以前 x 天
考虑贪心，每次加入一段值相等的数，如果还有免费额度就先用免费额度，否则尝试拆掉原来的匹配并新生成两个免费额度。如果被拆除的匹配 \(i\to j\) 就是拆除 \(j\) 的匹配而获得的，那么复原 \(j\) 的匹配可能更优，这里需要处理。
代码
| #include<iostream>
#include<algorithm>
#include<queue>
#define int long long
using namespace std;
const int N = 5e5 + 10;
int n, ans;
int a[N];
int sta[N], top;
priority_queue<int, vector<int>, greater<int>> que;
signed main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
for(int i = n, cnt; i >= 1; i -= cnt) {
cnt = 1;
for(int j = i - 1; j >= 1 && a[j] == a[i]; j--) ++cnt;
int t = n - i - que.size() * 2;
for(int j = 1; j <= min(cnt, t); j++) sta[++top] = a[i];
if(cnt > t) {
int r = cnt - t;
while(!que.empty() && que.top() < 2 * a[i] && r >= 2) {
ans += que.top();
if(que.top() >= a[i]) {
sta[++top] = 2 * a[i] - que.top();
sta[++top] = que.top();
} else {
sta[++top] = a[i], sta[++top] = a[i];
}
r -= 2;
que.pop();
}
if(r && !que.empty() && que.top() < a[i]) {
ans += que.top(); que.pop();
sta[++top] = a[i];
r--;
}
ans += r * a[i];
}
while(top) que.push(sta[top--]);
}
cout << ans << '\n';
return 0;
}
|
将问题转化为前 \(t\) 秒 \((x,y)\) 经过了多少货物。发现 \((x,y)\) 有恰好一半转移到右边，恰好一半转移到下面，因此可以 \(O(n^2)\) 求出答案。
枚举哪个区间的数字是没有动过的，之后对所有数组分讨 9 种情况，最后一种用 2-SAT 解决即可。
如果一次跳跃的两个端点 \(i\to j\) 满足 \([i,j]\) 的最小值不在端点处，那么可以先跳到最小值，代价变小。因此 \(i,j\) 中至少一个是区间最小值。
对于一个区间，考虑一种最朴素的策略：一步一步跳过去，总代价不超过 \(n\times d\)（\(d=j-i\)）；而一次跳过去，代价为 \(a_i\times d^2\)。因此跳一次需要满足 \(a_i\times d^2\le nd\)，即 \(d\le\frac{n}{a_i}\)。对 \(a_i\) 根号分治，如果 \(a_i\ge \sqrt n\)，那么直接暴力转移；否则以 \(a_i\)（值）同时为区间最小值和左端点的区间总数是 \(O(n)\) 级别的，而 \(a_i\) 也只有 \(\sqrt n\) 种，因此时间复杂度是对的。