自动搬运

查看原文

来自洛谷，原作者为

	CodyTheWolf ACM在役的小动物！qwq

搬运于2025-08-24 21:32:11，当前版本为作者最后更新于2018-12-23 19:33:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

开头小广告：自己做的一个模板库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;
}