题解 P1946 【Olympic_NOI导刊2009提高（1）】

· · 题解

来自攻略组成员的首发题解：

开头小广告：自己做的一个模板库OwO

算法考察：线性规划

思路：

直接暴力三层循环是稳稳的O(1000^3)也就是O(10^9)，我们考虑优化最后一个循环。

到第3个循环，也就是枚举Cu的分数时，我们可以把前面Au和Ag的分数先给每个队伍算好：

设第i个队伍的总分数在只有Au和Ag分数时是tot_i，拥有的Cu数量是cu_i

如果第一个队伍要赢过第i个队伍，设Cu的分数是k，明显有不等式：

tot_1+k \times cu_1 \geq tot_i+k\times cu_i

化简:

k \geq \frac{tot_i-tot_1}{cu_1-cu_i}

但是这里cu1-cu_i是可0可负的，因此我们要分类讨论：

cu_1-cu_i > 0 我们有：k \geq \frac{tot_i-tot_1}{cu_1-cu_i}

cu_1-cu_i < 0 我们有：k \leq \frac{tot_i-tot_1}{cu_1-cu_i}

cu_1-cu_i = 0 我们有：当tot_i \geq tot_1时，1队伍绝对获胜（分数相等1排在最前）

我们想象一个数轴，作关于这些不等式的垂线，我们从1出发（积分最少为1）。

对于小于等于的不等式，我们一开始就是满足的，先累加进我们的答案，当我们穿过他（而不是停留在这）时，减去一个答案。因为我们都是整数答案，所以小于等于号的右边要向下取整。

对于大于等于的不等式，我们停留在这的时候，我们的答案便加上一个。因为我们都是整数答案，所以大于等于号的右边要向上取整。

对于数轴，我们不需要一个一个单位走，按照不等式右边排序即可，然后就可以按照n个不等式，从小到大跳着走了（反正中间也不可能出现不等式了）。

每跳到一个不等式，可能有其他的不等式跟这个不等式在同一个单位，这时候要全部处理完毕才能更新答案，很显然。

注意：

1.题目条件：Au分数大于等于Ag分数大于等于Cu分数，注意枚举的范围，也要注意最后一个循环用线性规划优化时不要超过Ag分数了。

2.有些条件是可以提前预判掉的，比如k<=0是不可能到达的条件。

Code

// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 16, MAX = 1e3;

typedef pair<int, bool> pib;
int au[MAXN], ag[MAXN], cu[MAXN];
int tot[MAXN];
pib temp[MAXN];

int n;

int ans = 0, ansx = 1, ansy = 1, ansz = 1;

inline bool Compare(pib a, pib b)
{
    return a.first < b.first;
}

inline void Solve(int x, int y)
{
    int num = 0, tail = 0;

    for (int i = 1; i <= n; i++)
        tot[i] = au[i] * x + ag[i] * y;

    for (int i = 2; i <= n; i++)
    {
        double delta = tot[i] - tot[1], k = cu[1] - cu[i];

        if (!k)
        {
            num += (tot[i] >= tot[1]);
            continue;
        }
        if (k < 0 && delta > 0)
            continue;
        if (k > 0 && delta < 0)
        {
            num++;
            continue;
        }

        if (k > 0)
            temp[++tail] = make_pair(ceil(delta / k), true);
        else
            temp[++tail] = make_pair(floor(delta / k), false);
    }

    sort(temp + 1, temp + tail + 1, Compare);

    for (int i = 1; i <= tail; i++)
        if (!temp[i].second)
            num++;

    for (int i = 1; i <= tail; i++)
    {
        int j = i, cnt = 0;
        while (temp[j + 1].first == temp[i].first && j + 1 <= tail)
            j++;

        for (int k = i; k <= j; k++)
            if (temp[k].second)
                num++;
            else
                cnt++;

        if (num > ans && temp[i].first > 0 && temp[i].first <= y)
            ans = num, ansx = x, ansy = y, ansz = temp[i].first;

        i = j, num -= cnt;
    }

    return;
}

signed main(void)
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d %d %d", au + i, ag + i, cu + i);

    for (int i = 1; i <= MAX; i++)
        for (int j = 1; j <= i; j++)
            Solve(i, j);

    printf("%d %d %d\n", ansx, ansy, ansz);

    return 0;
}