伊斯坦布尔的帮派Gangs of Istanbull
题目链接：https://www.luogu.org/problem/P3064
数据范围：略。
题解：
这个题其实分为两问，第一问是$YES$、$NO$和最大值，第二问是最小字典序方案。
整体思路肯定是，后$2sim m$的帮派先自行抵消，最少能剩下多少奶牛，然后再用$1$去抵消。
先说第一问：
问题就相当于求$k$堆奶牛最少抵消成多少头。
这个最傻逼的做法就是维护一个大根堆，把$2sim m$都扔进去。
然后每次取出人数最多的两个帮派，让它俩互相抵消一次，再扔回堆里，这是$O(nlogn)$的。
再来看第二问：
我们发现，如果按照第一问的思路，第二问根本就没法做。
因为第一问的过程我们根本就没办法掌控，但是它给了我们一些启发。
再画几组小数据我们发现，最少剩多少奶牛其实只和这$2sim 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
", 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
", j);
id = j, now = 1;
a[j] -- ;
update(j, -1, 1, m, 1);
continue;
}
if (id == j) {
printf("%d
", 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
", j);
update(j, -1, 1, m, 1);
a[j] -- ;
now -- ;
if (!now) {
id = 0;
}
}
else {
printf("%d
", mdlmxid);
update(mdlmxid, -1, 1, m, 1);
a[mdlmxid] -- ;
now -- ;
if (!now) {
id = 0;
}
}
}
for (int i = 1; i <= a[1]; i ++ ) {
printf("%d
", 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
", j);
id = j, now = 1;
a[j] -- ;
update(j, -1, 1, m, 1);
continue;
}
if (id == j) {
printf("%d
", 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
", j);
update(j, -1, 1, m, 1);
a[j] -- ;
now -- ;
if (!now) {
id = 0;
}
}
else {
printf("%d
", mdlmxid);
update(mdlmxid, -1, 1, m, 1);
a[mdlmxid] -- ;
now -- ;
if (!now) {
id = 0;
}
}
}
// puts("Shit");
// printf("%d
", a[1]);
for (int i = 1; i <= a[1]; i ++ ) {
printf("%d
", 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
", id);
}
for (int i = 2; i < id; i ++ ) {
for (int j = 1; j <= a[i]; j ++ ) {
printf("%d
", i);
}
for (int j = 1; j <= a[i]; j ++ ) {
printf("%d
", id);
}
}
int mdlsum = 0;
for (int i = id + 1; i <= m; i ++ ) {
mdlsum += a[i];
}
for (int i = 1; i <= mdlsum; i ++ ) {
printf("%d
", id);
}
for (int i = id + 1; i <= m; i ++ ) {
for (int j = 1; j <= a[i]; j ++ ) {
printf("%d
", i);
}
}
for (int i = 1; i <= a[1] - re; i ++ ) {
puts("1");
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
小结：好题好题，但是细节有点点多。考试的时候没拿到$flag=2$的点，原因是$for$循环的问题。所以如果一个题有多种情况，最好每种情况都试几组小样例。