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
这个坑让我搞了一个下午,最后发现是题解的锅。