51Nod-1494-选举拉票

描述

题解

线段树的题倒是做过一些，但是和扫描线组合的倒是第一次做，以前甚至不知道什么叫做扫描线，做了这个题感觉有那么丢丢感觉了。

首先，我们默认要拉所有选民，然后开始减少要拉的选民数。这是中心思想。具体的实现方式是，我们先对每个人的选民进行代价排序，然后扫描出来每个候选人的选民的代价 rank ，同等 rank 的放在一起，你要是问什么是 rank 的话，举个最简单的例子，有 A、B、C 三个候选人，选民叛变的代价从大到小排序后分别是 11，10，9 、 8，7，3，1 、 15，2 ，那么根据 rank 分组我们可以分为四组， rank1 的组有 11，8，15 ， rank2 的组有 10，7，2 ， rank3 的组有 9，3 ， rank4 的组有 1 。这就是扫描线的过程，我想不难理解吧……然后呢？我们开始考虑剔除一些不必要的选民，当然是优先剔除每个候选人的叛变代价最大的选民，也就是说逐次剔除 rank：1、2、3、4 的选民，每次剔除一组选民后，我们都要判断，此时剩下的选民和其他候选人目前拥有的最多的选民数目，这个数目是多少呢？自然是我们剔除的次数了。如果说，我们此时的选民小于等于其他候选人目前拥有最多的选民数目，我们怎么办？这个部分很好想，当然是从剔除的所有选民中选取最小的若干个选民喽，那么这部分就是需要用到线段树来处理了，当然，用树状数组也是可以的。

我想我描述的已经足够清楚了，现在再看代码应该没有什么障碍了，所以就这样吧！

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

#define lson rt << 1
#define rson rt << 1 | 1

using namespace std;

const int MAXA = 1e5 + 10;
const int MAXB = 1e4 + 10;

int n;
int tree[MAXB << 2];
int num[MAXB << 2];
vector<int> vi_b[MAXA];
vector<int> vi_t[MAXA];

void update(int rt, int l, int r, int x)
{
    if (l == r)
    {
        num[rt]++;
        tree[rt] += l;
        return ;
    }
    int m = (l + r) >> 1;
    if (x <= m)
    {
        update(lson, l, m, x);
    }
    else
    {
        update(rson, m + 1, r, x);
    }

    tree[rt] = tree[lson] + tree[rson];
    num[rt] = num[lson] + num[rson];
}

int query(int rt, int l, int r, int x)
{
    if (l == r)
    {
        return l * x;
    }

    int m = (l + r) >> 1;
    if (x == num[lson])
    {
        return tree[lson];
    }
    if (x > num[lson])
    {
        return tree[lson] + query(rson, m + 1, r, x - num[lson]);
    }
    else
    {
        return query(lson, l, m, x);
    }
}

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int main()
{
    scanf("%d", &n);

    int ans = 0, mx_a = 0, mx_b = 1, a, b;
    for (int i = 1; i <= n; i++)
    {
        scan_d(a), scan_d(b);
        if (b == 0)
        {
            continue;
        }

        ans += b;
        mx_a = max(mx_a, a);
        mx_b = max(mx_b, b);
        vi_b[a].push_back(b);
    }

    int mx_c = 0;
    for (int i = 1; i <= mx_a; i++)
    {
        if (vi_b[i].size())
        {
            sort(vi_b[i].begin(), vi_b[i].end(), greater<int>());

            mx_c = max(mx_c, (int)vi_b[i].size());
            for (int j = 0; j < vi_b[i].size(); j++)
            {
                vi_t[j].push_back(vi_b[i][j]);
            }
        }
    }

    int k = n, res = ans;
    for (int i = 0; i < mx_c; i++)
    {
        k -= vi_t[i].size();
        for (int j = 0; j < vi_t[i].size(); j++)
        {
            update(1, 1, mx_b, vi_t[i][j]);
            res -= vi_t[i][j];
        }

        int tmp = 0, mn;
        if (k <= i + 1)
        {
            mn = min(i + 2 - k, n);     // 还差 mn 票
            tmp = query(1, 1, mx_b, mn);// 取最小的 mn 票
        }

        ans = min(ans, res + tmp);
    }

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

    return 0;
}