T1 总结
赛时总结
若至题。一眼顶针
题目思路
上数据结构 map
题目代码
无
T2 总结
赛时总结
贪心策略错误，难度排序排成了满意度排序
题目思路
贪，按照难度排序
题目代码
1
2
3
4
5
6
7
8
9
10
11
| sort(con + 1, con + c + 1);
sort(pro + 1, pro + p + 1);
ll ans = 0;
ll mx = 0, j = 0;
for(int i = 1; i <= p; i++) {
while(con[j + 1].first <= pro[i].first && j <= c) {
mx = max(mx, con[++j].second);
}
ans += max(0LL, mx - pro[i].second);
}
printf("%lld", ans);
|
T3 总结
赛时总结
水题，典中典。
题目思路
不难发现横竖无关，单独处理后合并答案
题目代码
无
T4 总结
赛时总结
完全没有思路，部分分拿满
题目思路
对于绝对值考虑分解，情况分为左边，右边以及未选择。
枚举所有位置，动态维护左边右边以及未选集合，不断用未选集合更新左边，每向右跳动一个考虑右边是否会变成左边。模拟即可
题目代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| for(int i = 1; i <= k; i++) {
B.insert(*C.begin());
sumB += C.begin()->first;
C.erase(C.begin());
}
ll ans = 1e18, pos = 0;
for(int i = 1; i <= n; i++) {
while(!A.empty() && !C.empty() && A.rbegin()->first + i > C.begin()->first - i) {
sumA -= A.rbegin()->first;
A.erase(*A.rbegin());
sumB += C.begin()->first;
B.insert(*C.begin());
C.erase(C.begin());
}
ll now = sumA + sumB + (ll)A.size() * i - (ll)B.size() * i;
if(now < ans) {
ans = now, pos = i;
}
if(B.count(make_pair(a[i] + i, i))) {
A.insert(make_pair(a[i] - i, i));
sumA += a[i] - i;
B.erase(make_pair(a[i] + i, i));
sumB -= a[i] + i;
}
if(C.count(make_pair(a[i] + i, i))) {
C.erase(make_pair(a[i] + i, i));
}
}
printf("%lld %lld", pos, ans);
|
