2017年浙江工业大学大学生程序设计迎新赛预赛 H

题目描述

        “伟大的勇士兔栽栗女王，所有栗子看到您都不寒而栗，但也非常尊重您。您骑着威风凛凛的小白兔，带领兔栽栗们奋勇前行。伟大史诗告诉我们，烈兔勇栗从大草原飞奔出来，冲在每场战争的前线——无论您在哪里，他们都能找到您。骑小白兔飞驰吧，凶猛的女王，但愿您有真正的朋友和软弱的敌人。”
        今天，冰雪聪明的栗酱终于玩到了她梦寐很久的文明游戏。
        不过作为一个萌新，兔头獐脑的栗酱自然不愿意第一次玩就遇到一个尴尬的开局，于是希望通过你来寻找一个完美开局。

已知开始时场上有n个国家，每个国家有一个初始人口基数ai，2个人口基数均不为0的国家间可以进行一场战争，而战争会使这两个国家的人口基数分别下降1，任意2个国家之间最多进行一场战争。
完美开局的定义是：存在一种战争集合，当这些战争完成以后，所有国家的人口基数总和取得最小值。
现在请你输出完美开局下所有国家的人口基数之和。

输入描述:

第一行一个数T，表示有T组数据。

对于每组数据，第一行输入一个数n，表示国家的数量，接下来一行输入n个数，

a1,a2,…,an, 其中ai表示第i个国家的初始人口基数。

每两个相邻的数之间用空格隔开。

输出描述:

对于每一个询问，输出一个数，即完美开局下所有国家的人口基数之和。

示例1

输入

2

4

3 3 3 3

8

3 4 3 4 1 3 3 4

输出

0

1

说明

对于第一个样例：
国家1与国家2之间进行一场战争，剩下的人口基数为：2 2 3 3，
国家1与国家3之间进行一场战争，剩下的人口基数为：1 2 2 3，
国家1与国家4之间进行一场战争，剩下的人口基数为：0 2 2 2，
国家2与国家3之间进行一场战争，剩下的人口基数为：0 1 1 2，
国家2与国家4之间进行一场战争，剩下的人口基数为：0 0 1 1，
国家3与国家4之间进行一场战争，剩下的人口基数为：0 0 0 0。
任意两个国家之间恰好分别发生一场战争，剩余人口基数和取得最小值0。

备注:

T≤10

1≤n≤105

1≤ai≤n

题解

线段树，贪心，Havel-Hakimi定理。

操作步骤和Havel-Hakimi定理相同，只是要拿线段树优化一下操作。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100000 + 10;

int T, n;

int a[maxn];

int s[maxn * 4];

int f[maxn * 4];

void pushDown(int rt) {

  if(f[rt] == 0) return;

  s[2 * rt] = s[2 * rt] - f[rt];

  s[2 * rt + 1] = s[2 * rt + 1] - f[rt];

  f[2 * rt] = f[2 * rt] + f[rt];

  f[2 * rt + 1] = f[2 * rt + 1] + f[rt];

  f[rt] = 0;

}

void pushUp(int rt) {

  s[rt] = max(s[2 * rt], s[2 * rt + 1]);

}

void build(int l, int r, int rt) {

  f[rt] = 0;

  if(l == r) {

    s[rt] = a[l];

    return;

  }

  int mid = (l + r) / 2;

  build(l, mid, 2 * rt);

  build(mid + 1, r, 2 * rt + 1);

  pushUp(rt);

}

int get(int p, int l, int r, int rt) {

  if(l == r) {

    return s[rt];

  }

  int res;

  int mid = (l + r) / 2;

  pushDown(rt);

  if(p <= mid) res = get(p, l, mid, 2 * rt);

  else res = get(p, mid + 1, r, 2 * rt + 1);

  pushUp(rt);

  return res;

}

void update(int L, int R, int val, int l, int r, int rt) {

  if(L <= l && r <= R) {

    f[rt] = f[rt] + val;

    s[rt] = s[rt] - val;

    return;

  }

  int mid = (l + r) / 2;

  pushDown(rt);

  if(L <= mid) update(L, R, val, l, mid, 2 * rt);

  if(R > mid) update(L, R, val, mid + 1, r, 2 * rt + 1);

  pushUp(rt);

}

int first(int l, int r, int rt) {

  if(l == r) {

    return l;

  }

  int mid = (l + r) / 2;

  int res;

  pushDown(rt);

  if(s[2 * rt] > 0) res = first(l, mid, 2 * rt);

  else res = first(mid + 1, r, 2 * rt + 1);

  pushUp(rt);

  return res;

}

int main() {

  scanf("%d", &T);

  while(T --) {

    scanf("%d", &n);

    for(int i = 1; i <= n; i ++) {

      scanf("%d", &a[i]);

    }

    sort(a + 1, a + 1 + n);

    build(1, n, 1);

    for(int i = n; i >= 1; i --) {

      int y = first(1, n, 1);

      if(y >= i) break;

      int x = get(i, 1, n, 1);

      if(x >= i - y) {

        update(i, i, i - y, 1, n, 1);

        update(y, i - 1, 1, 1, n, 1);

      } else {

        update(i, i, x, 1, n, 1);

        update(i - x, i - 1, 1, 1, n, 1);

        if(get(i - x - 1, 1, n, 1) > get(i - x, 1, n, 1)) {

          int L1, R1 = i - x - 1;

          int L2 = i - x, R2;

          int left, right;

          left = y, right = i - x - 1;

          while(left <= right) {

            int mid = (left + right) / 2;

            if(get(mid, 1, n, 1) < get(i - x - 1, 1, n, 1)) {

              left = mid + 1;

            } else {

              right = mid - 1;

              L1 = mid;

            }

          }

          left = i - x, right = i - 1;

          while(left <= right) {

            int mid = (left + right) / 2;

            if(get(mid, 1, n, 1) > get(i - x, 1, n, 1)) {

              right = mid - 1;

            } else {

              left = mid + 1;

              R2 = mid;

            }

          }

          //[L1, R1] [L2, R2];

          if(R1 - L1 == R2 - L2) {

            update(L1, R1, 1, 1, n, 1);

            update(L2, R2, -1, 1, n, 1);

          } else if(R1 - L1 > R2 - L2) {

            update(L2, R2, -1, 1, n, 1);

            update(L1, L1 + R2 - L2, 1, 1, n, 1);

          } else {

            update(L1, R1, 1, 1, n, 1);

            update(R2 + L1 - R1, R2, -1, 1, n, 1);

          }

        }

      }

    }

    long long ans = 0;

    for(int i = 1; i <= n; i ++) {

      ans = ans + (long long)get(i, 1, n, 1);

    }

    printf("%lld\n", ans);

  }

  return 0;

}

巴特西

2017年浙江工业大学大学生程序设计迎新赛预赛 H - 栗酱的文明

题目描述

输入描述:

输出描述:

输入

输出

说明

备注:

题解

最新文章

热门文章