题解害淫不浅

回复帖子

@xbz也能爆装备 2020-09-16 15:57 回复

QAQ

#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;
}

这个是题解中的第一篇,但是对于这组数据

4
2 5 6
9 3 2
9 9 6
3 1 7

来讲 正确答案应为1 1 1

但是输出是 3 1 1

这个坑让我搞了一个下午,最后发现是题解的锅。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。