基本思路：对于每个i，选出最小的前i个值，越大的值放在越前面，即可得到最小的penalty
假设dp[i]表示前i个元素能获得的最小penalty，那么dp[i + m] = dp[i] + sum[1 : i+m]，即[i+1, i+m]放在第一天，其他的以此往后移一天
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 2e5+7;
5 const ll mod = 998244353;
6 #define afdafafafdafaf y1;
7 int ar[maxn], n, m;
8
9 ll p[maxn], s[maxn];
10 int main()
11 {
12 scanf("%d%d", &n, &m);
13 for(int i=1;i<=n;i++)scanf("%d", ar+i);
14 sort(ar+1, ar+n+1);
15 for(int i=1;i<=n;i++)p[i] = p[i-1] + ar[i];
16 //for(int i=1;i<=n;i++)printf("%lld%c", p[i], i==n?'\n' : ' ');
17 for(int i=1;i<=m;i++){
18 ll ins = i, x = p[i];
19 while(ins <= n){
20 s[ins] = x;
21 ins += m;
22 if(ins <= n)x += p[ins];
23 }
24 }
25 for(int i=1;i<=n;i++)printf("%lld%c", s[i], i==n?'\n' : ' ');
26 return 0;
27 }
View Code
边排序+并查集
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 2e5+7;
5 const ll mod = 998244353;
6 #define afdafafafdafaf y1;
7 int ar[maxn], n, m;
8
9 pair<int,int> p[maxn];
10 int f[maxn];
11 int findx(int x){
12 return f[x] == x ? x : f[x] = findx(f[x]);
13 }
14 int main()
15 {
16 scanf("%d%d", &n, &m);
17 for(int i=1;i<=n;i++)f[i] = i;
18 for(int i=1;i<=m;i++){
19 int a,b;scanf("%d%d", &a, &b);
20 if(a > b)swap(a, b);
21 p[i].first = a;
22 p[i].second = b;
23 a = findx(a);
24 b = findx(b);
25 f[a] = b;
26 }
27 sort(p + 1, p + m + 1);
28 int pa = 0, pb = 0;
29 p[m+1].first = int(1e9);
30 //cout<<p[m+1].first<<'\n';
31 int ans=0;
32 for(int i=1;i<=m+1;i++){
33 //cout<<"i = " << i << ' ' << p[i].first<<" "<<p[i].second<<"\n";
34 if(p[i].first > pb){
35 int x = pa;
36 //cout<<pa<<" "<<pb<<"\n";
37 for(int j=pa+1;j<=pb;j++){
38 x = findx(x);
39 int y = j;
40 y = findx(y);
41 if(x != y){
42 f[x] = y;
43 ans++;
44 }
45 }
46 pa = p[i].first;
47 pb = p[i].second;
48 }
49 else{
50 pb = max(pb, p[i].second);
51 }
52 }
53 printf("%d\n", ans);
54 return 0;
55 }
View Code
按照每个区间的头尾排序
正序遍历，求出覆盖前i个节点所需要的最小花费，答案即que(m)
因为两段如果要相接的话，前一段的头一定在后一段的头的前面，所以可以证明排序后正序遍历是正确的。
（比赛的时候求了前后缀，遍历相加，所以代码里是que_l，忽略即可
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 2e5+7;
5 const ll mod = 998244353;
6 #define afdafafafdafaf y1;
7 int ar[maxn], n, m;
8
9 int x[maxn], s[maxn], l[maxn], r[maxn];
10 ll lp[maxn], rp[maxn];
11 pair<int,int> p[maxn];
12 int lmn[maxn << 2], rmn[maxn << 2];
13 void set_l(int x, int val){
14 while(x > 0){
15 if(val >= lmn[x])break;
16 lmn[x] = min(lmn[x], val);
17 x -= x & (-x);
18 //cout<<"x_set = " << x << '\n';
19 }
20 }
21 int que_l(int x){
22 if(x == 0)return 0;
23 int ans = m;
24 while(x <= m){
25 ans = min(ans, lmn[x]);
26 x += x & (-x);
27 //cout<<"x_que = " << x << '\n';
28 }
29 return ans;
30 }
31
32 int main()
33 {
34 scanf("%d%d", &n, &m);
35 for(int i=1;i<=n;i++)scanf("%d%d", x + i, s + i);
36 for(int i=1;i<=n;i++){
37 int a = x[i], b = s[i];
38 p[i].first = max(1, a - b);
39 p[i].second = min(m, a + b);
40 }
41 sort(p+1, p+n+1);
42 for(int i=1;i<=n;i++){
43 l[i] = p[i].first;
44 r[i] = p[i].second;
45 }
46 for(int i = 0; i < (maxn << 2); i++)lmn[i] = rmn[i] = m;
47 set_l(0, 0);
48 for(int i=1;i<=n;i++){
49 int a = l[i], b = r[i], ins = 0;
50 while(a >= 1 || b <= m){
51 int l_a = que_l(a - 1);
52 set_l(b, l_a + ins);
53 if(a == 1 && b == m)break;
54 if(a > 1)a--;
55 if(b < m)b++;
56 ins++;
57 }
58 }
59 printf("%d\n", que_l(m));
60 return 0;
61 }
View Code
F - Cheap Robot
不会