Guard Duty (medium) Codeforces

https://codeforces.com/contest/958/problem/E2

首先求出N个时刻的N-1个间隔长度，问题就相当于在这些间隔中选K个数，相邻两个不能同时选，要求和最小

方法1：

一个K^2的做法，有一定技巧

https://www.cnblogs.com/void-f/p/8867585.html

方法2：

是可撤销贪心的模板？

就是贪心的选权值最小的，但是在选完某一个位置i后把它前一个没有被删的位置pre[i]和后一个没有被删的位置nxt[i]删掉，将i的权值变为(-(i原来的权值)+(pre[i]原来的权值)+(nxt[i]原来的权值))，表示如果再选一次这个位置，就相当于不选i，改为选pre[i]和nxt[i]

这样子搞是因为：由于每次是贪心的选权值最小的i，则单独选pre[i]和nxt[i]中任意一个都不可能比选i更优，只有当同时选pre[i]和nxt[i]时可能比选i要优

细节并不能搞清楚...然而，这个算法运行得很正确

有一个要注意的：如果选出的是最靠边上的i，那么显然i一定在最优解中（因为改为选i旁边的一定不会更优），直接把自身和与其相邻的删掉即可

可以搞一个链表+堆维护这个东西

错误记录：链表写错

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<vector>
 5 #include<set>
 6 using namespace std;
 7 #define fi first
 8 #define se second
 9 #define mp make_pair
10 #define pb push_back
11 typedef long long ll;
12 typedef unsigned long long ull;
13 typedef pair<int,int> pii;
14 struct E
15 {
16     int nxt,pre,d;
17 }e[500100];
18 int a[500100];
19 int K,n;
20 set<pii> s;
21 set<pii>::iterator i1;
22 int an;
23 int main()
24 {
25     int i,x,y;pii t;
26     scanf("%d%d",&K,&n);
27     for(i=1;i<=n;i++)    scanf("%d",&a[i]);
28     sort(a+1,a+n+1);
29     for(i=1;i<n;i++)    a[i]=a[i+1]-a[i];
30     n--;
31     for(i=1;i<=n;i++)
32     {
33         e[i].nxt=i+1;
34         e[i].pre=i-1;
35         e[i].d=a[i];
36         s.insert(mp(e[i].d,i));
37     }
38     e[n].nxt=e[1].pre=0;
39     for(i=1;i<=K;i++)
40     {
41         i1=s.begin();
42         t=*i1;s.erase(i1);
43         x=t.fi;y=t.se;
44         an+=x;
45         x=-x;
46         if(!e[y].pre||!e[y].nxt)
47         {
48             if(e[y].pre)
49             {
50                 s.erase(mp(e[e[y].pre].d,e[y].pre));
51                 e[e[e[y].pre].pre].nxt=0;
52             }
53             if(e[y].nxt)
54             {
55                 s.erase(mp(e[e[y].nxt].d,e[y].nxt));
56                 e[e[e[y].nxt].nxt].pre=0;
57             }
58         }
59         else
60         {
61             x+=e[e[y].pre].d;x+=e[e[y].nxt].d;
62             s.erase(mp(e[e[y].pre].d,e[y].pre));
63             s.erase(mp(e[e[y].nxt].d,e[y].nxt));
64             e[y].pre=e[e[y].pre].pre;e[e[y].pre].nxt=y;
65             e[y].nxt=e[e[y].nxt].nxt;e[e[y].nxt].pre=y;
66             e[y].d=x;
67             s.insert(mp(e[y].d,y));
68         }
69     }
70     printf("%d",an);
71     return 0;
72 }

View Code

方法3：

为什么说是什么带权二分？以后再说

以下题改一下以上代码读入中n和K的顺序就可以A掉了？？

https://www.lydsy.com/JudgeOnline/problem.php?id=1150

bzoj 2151 种树

https://www.lydsy.com/JudgeOnline/problem.php?id=2151

洛谷P1792

https://www.luogu.org/problemnew/show/P1792

（另有一样的题(编译优化)：http://210.33.19.103/contest/982/problem/5）

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<vector>
 5 #include<set>
 6 using namespace std;
 7 #define fi first
 8 #define se second
 9 #define mp make_pair
10 #define pb push_back
11 typedef long long ll;
12 typedef unsigned long long ull;
13 typedef pair<ll,int> pli;
14 struct E
15 {
16     int nxt,pre;ll d;
17 }e[500100];
18 int a[500100];
19 int n,m;
20 set<pli> s;
21 set<pli>::iterator i1;
22 ll an;
23 int main()
24 {
25     int i,y;ll x;pli t;
26     scanf("%d%d",&n,&m);
27     if(m>n/2)
28     {
29         puts("Error!");
30         return 0;
31     }
32     for(i=1;i<=n;i++)    scanf("%d",&a[i]);
33     for(i=1;i<=n;i++)
34     {
35         e[i].nxt=i+1;
36         e[i].pre=i-1;
37         e[i].d=a[i];
38         s.insert(mp(e[i].d,i));
39     }
40     e[n].nxt=1;e[1].pre=n;
41     for(i=1;i<=m;i++)
42     {
43         i1=s.end();--i1;
44         t=*i1;s.erase(i1);
45         x=t.fi;y=t.se;
46         an+=x;
47         x=-x;
48         x+=e[e[y].pre].d;x+=e[e[y].nxt].d;
49         s.erase(mp(e[e[y].pre].d,e[y].pre));
50         s.erase(mp(e[e[y].nxt].d,e[y].nxt));
51         e[y].pre=e[e[y].pre].pre;e[e[y].pre].nxt=y;
52         e[y].nxt=e[e[y].nxt].nxt;e[e[y].nxt].pre=y;
53         e[y].d=x;
54         s.insert(mp(e[y].d,y));
55     }
56     printf("%lld",an);
57     return 0;
58 }

View Code