伊斯坦布尔的帮派Gangs of Istanbull
题目链接:https://www.luogu.org/problem/P3064
数据范围:略。
题解:
这个题其实分为两问,第一问是$YES$、$NO$和最大值,第二问是最小字典序方案。
整体思路肯定是,后$2\sim m$的帮派先自行抵消,最少能剩下多少奶牛,然后再用$1$去抵消。
先说第一问:
问题就相当于求$k$堆奶牛最少抵消成多少头。
这个最傻逼的做法就是维护一个大根堆,把$2\sim m$都扔进去。
然后每次取出人数最多的两个帮派,让它俩互相抵消一次,再扔回堆里,这是$O(nlogn)$的。
再来看第二问:
我们发现,如果按照第一问的思路,第二问根本就没法做。
因为第一问的过程我们根本就没办法掌控,但是它给了我们一些启发。
再画几组小数据我们发现,最少剩多少奶牛其实只和这$2\sim m$中的最大值有关。
这是显然的,那么我们假设这些奶牛的和为$sum$,最大值为$mx$,分两种情况讨论:
第一种:$mx > \frac{sum}{2}$。
这种就比较简单,因为所有的非最大值奶牛一定是要和最大值相抵消的。
那么我们把答案大小的$1$号放在最后,剩下的随便搞搞基就好,具体看代码。
第二种:$mx \le \frac{sum}{2}$。
这种的话,最少会剩下$sum \& 1$头,假设是$0$。
那么所有的$1$奶牛都得扔在后面,我们只需要考虑剩下的帮派怎么互相抵消就好。
考虑每次贪心。
假设现在已经决定了前$i - 1$头奶牛的顺序,剩下$now$头属于帮派$id$的奶牛,我们考虑$i$位置。
首先,取出来最小的有奶牛的帮派和最大的帮派两个。
如果最小的帮派放在了位置$i$,与$now$和$id$做了做抵消之后,剩下的奶牛仍然满足$Max \le \frac{Sum}{2}$,我们就放最小的。
显然如果最小的不行,不是最大值不是最小值的其他任何数都不行(除了$id$,可以做一下特判)。
如果都不行,那么这个位置只能是最大值,我们就把最大值所在的帮派的奶牛数$--$,然后考虑位置$i + 1$即可。
这时候,我们想一想怎么能拿出来最大值最小值呢?还要支持单点修改?那就维护一个线段树好了。
代码:
#include <bits/stdc++.h> #define N 1000010 #define ls p << 1 #define rs p << 1 | 1 using namespace std; char *p1, *p2, buf[100000]; #define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ ) int rd() { int x = 0, f = 1; char c = nc(); while (c < 48) { if (c == '-') f = -1; c = nc(); } while (c > 47) { x = (((x << 2) + x) << 1) + (c ^ 48), c = nc(); } return x * f; } int a[N]; int sum[N << 2], mx[N << 2]; inline void pushup(int p) { mx[p] = max(mx[ls], mx[rs]); sum[p] = sum[ls] + sum[rs]; } void update(int x, int v, int l, int r, int p) { if (l == r) { sum[p] += v, mx[p] += v; return; } int mid = (l + r) >> 1; if (x <= mid) { update(x, v, l, mid, ls); } else { update(x, v, mid + 1, r, rs); } pushup(p); } int query_id(int l, int r, int p) { if (l == r) { return l; } int mid = (l + r) >> 1; if (sum[ls]) { return query_id(l, mid, ls); } else { return query_id(mid + 1, r, rs); } } int query_mx(int l, int r, int p) { if (l == r) { return l; } int mid = (l + r) >> 1; if (mx[ls] >= mx[rs]) { return query_mx(l, mid, ls); } else { return query_mx(mid + 1, r, rs); } } int main() { // freopen("gangs.in", "r", stdin); // freopen("gangs.out", "w", stdout); int n = rd(), m = rd(); for (int i = 1; i <= m; i ++ ) { a[i] = rd(); } int Sum = n - a[1], mx = 0; for (int i = 2; i <= m; i ++ ) { mx = max(mx, a[i]); } int re; int flag = 0; if (mx <= Sum / 2) { flag = 1; re = Sum & 1; if (re) { flag = 2; } } else { int mdl = Sum - mx; re = mx - mdl; flag = 3; } if (re >= a[1]) { puts("NO"); return 0; } puts("YES"); printf("%d\n", a[1] - re); if (flag == 1) { // puts("Fuck"); for (int i = 2; i <= m; i ++ ) { update(i, a[i], 1, m, 1); } int id = 0, now = 0; for (int i = 1; i <= n - a[1]; i ++ ) { int j = query_id(1, m, 1); if (!id) { printf("%d\n", j); id = j, now = 1; a[j] -- ; update(j, -1, 1, m, 1); continue; } if (id == j) { printf("%d\n", j); now ++ ; a[j] -- ; update(j, -1, 1, m, 1); continue; } int mdlall = now + sum[1] - 2; // puts("SSSShit"); int mdlmxid = query_mx(1, m, 1); // cout << mdlall << ' ' << mdlmxid << endl ; int mdlmx = a[mdlmxid]; if (mdlmxid == j) { mdlmx -- ; } if (mdlmx <= mdlall / 2) { printf("%d\n", j); update(j, -1, 1, m, 1); a[j] -- ; now -- ; if (!now) { id = 0; } } else { printf("%d\n", mdlmxid); update(mdlmxid, -1, 1, m, 1); a[mdlmxid] -- ; now -- ; if (!now) { id = 0; } } } for (int i = 1; i <= a[1]; i ++ ) { printf("%d\n", 1); } } else if (flag == 2) { // puts("Fuck"); update(1, 1, 1, m, 1); for (int i = 2; i <= m; i ++ ) { update(i, a[i], 1, m, 1); } int id = 0, now = 0; int all = n - a[1] + 1; for (int i = 1; i <= all; i ++ ) { int j = query_id(1, m, 1); if (!id) { printf("%d\n", j); id = j, now = 1; a[j] -- ; update(j, -1, 1, m, 1); continue; } if (id == j) { printf("%d\n", j); now ++ ; a[j] -- ; update(j, -1, 1, m, 1); continue; } int mdlall = now + sum[1] - 2; int mdlmxid = query_mx(1, m, 1); int mdlmx = a[mdlmxid]; if (mdlmxid == j) { mdlmx -- ; } if (mdlmx <= mdlall / 2) { printf("%d\n", j); update(j, -1, 1, m, 1); a[j] -- ; now -- ; if (!now) { id = 0; } } else { printf("%d\n", mdlmxid); update(mdlmxid, -1, 1, m, 1); a[mdlmxid] -- ; now -- ; if (!now) { id = 0; } } } // puts("Shit"); // printf("%d\n", a[1]); for (int i = 1; i <= a[1]; i ++ ) { printf("%d\n", 1); } } else { int id = 2; for (int i = 2; i <= m; i ++ ) { if (a[i] > a[id]) { id = i; } } for (int i = 1; i <= re; i ++ ) { puts("1"); } for (int i = 1; i <= re; i ++ ) { printf("%d\n", id); } for (int i = 2; i < id; i ++ ) { for (int j = 1; j <= a[i]; j ++ ) { printf("%d\n", i); } for (int j = 1; j <= a[i]; j ++ ) { printf("%d\n", id); } } int mdlsum = 0; for (int i = id + 1; i <= m; i ++ ) { mdlsum += a[i]; } for (int i = 1; i <= mdlsum; i ++ ) { printf("%d\n", id); } for (int i = id + 1; i <= m; i ++ ) { for (int j = 1; j <= a[i]; j ++ ) { printf("%d\n", i); } } for (int i = 1; i <= a[1] - re; i ++ ) { puts("1"); } } // fclose(stdin); // fclose(stdout); return 0; }
小结:好题好题,但是细节有点点多。考试的时候没拿到$flag=2$的点,原因是$for$循环的问题。所以如果一个题有多种情况,最好每种情况都试几组小样例。