线性规划¶
我们有n个表达式 A_n=a_ix+b_i。使用基于n的算法如何快速求出一个x使得A_1的值的排名尽可能考虑前呢？
我们是用线性规划。
例题 #1 Olympic¶
奥运会正在如火如荼的进行着，金牌榜上也有许多队伍需要排名。你需要选择三个整数 \(P_g,P_s\) 和 \(P_b\)，分别表示每获得一块金、银、铜牌所对应得分。并且满足 \(1000 \ge P_g \ge P_s \ge P_b \ge 1\)。队伍将依据他们获得的分数进行排序（高分在前）。现在，为了使你所在的队伍排名尽可能的靠前，由你来选择 \(P_g,P_s,P_b\)。
输入格式
第一行一个整数 \(n\ (1\le n\le 15)\)，表示有 \(n\) 支队伍进行排名。
以下 \(n\) 行，每行三个整数 \(G,S,B\ (0\le G,S,B\le 10^5)\)，表示每只队伍获得的金、银、铜牌个数。
-
第一支队伍即为你所在的队伍；
-
分数相同时，你所在的队伍排名为最前。
输出格式
一行输出三个数 \(P_g,P_s,P_b\)，中间用空格隔开。
若有多组解，则输出 \(P_g\) 最小的解，若仍有多组，则输出 \(P_s\) 最小的解，若还有多组解，输出 \(P_b\) 最小的解。
枚举\(P_g,P_s\)，线性规划求出\(P_b\)。
考虑队伍1胜过队伍i的条件。设只有金牌和银牌时的得分为soc_i，那么有\(soc_1+kB_1≥soc_i+kB_i\)。变形得\(k≥\frac{soc_i-soc_1}{B_1-B_i}\)（若B_1-B_i<0则变号）。
接下来我们这样思考：一个不等式代表数轴上一个点，只有k在这个点右侧时（>）才有贡献。于是我们可以从数轴左侧往右扫描一边，经过分界点时将贡献加上/减去即可。
// Problem: P1946 Olympic
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1946
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
//
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long
#define pb push_back
#define itn int
#define ps second
#define pf first
#define rd read()
int read()
{
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v: a) cerr << v << ' ';
err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N=2e5+5;
const ull P=137;
const int INF=1e18+7;
/*
策略
*/
pair<int,int > t[N];
int tot;
int a[N],b[N],c[N];
int soc[N];
int an[6];
int ans=0;
int n;
// void check(int pa,int pb){
// int tot=0;
// int cnt=0;
// for(int i=1;i<=n;i++){
// soc[i]=a[i]*pa+b[i]*pb;
// if(i>1){
// if(c[i]==c[1]){
// if(soc[1]>=soc[i])cnt++;
// }if(c[i]<c[1]){
// t[++tot]={ceil((soc[i]-soc[1])/(c[1]-c[i])),1};
// }if(c[i]>c[1]){
// t[++tot]={floor((soc[i]-soc[1])/(c[1]-c[i])),-1};
// cnt++;
// }
// }
// }
// sort(t+1,t+tot+1);
// int beg=1;
// while(t[beg].pf<1&&beg<=tot){
// tot+=t[beg].ps;
// beg++;
// }
// if(beg>tot)return ;
// if(t[beg].pf>pb)return ;
// if(ans<tot){
// ans=tot;
// an[1]=pa,an[2]=pb,an[3]=t[beg].pf;
// }
// for(int i=beg;i<=tot;i++){
// if(t[i].pf>pb)break;
// int add=0,del=0;
// if(t[i].ps==1)add++;
// else del++;
// while(t[i].pf==t[i+1].pf&&i<tot){
// i++;
// if(t[i].ps==1)add++;
// else del++;
// }
// tot+=add;
// if(ans<tot){
// ans=tot;
// an[1]=pa,an[2]=pb,an[3]=t[i].pf;
// }
// tot-=del;
// }
// }
inline void check(int x, int y)
{
int num = 0, tail = 0;
for (int i = 1; i <= n; i++)
soc[i] = a[i] * x + b[i] * y;
for (int i = 2; i <= n; i++)
{
double p = soc[i] - soc[1], q = c[1] - c[i];
if (!q)
{
num += (soc[i] >= soc[1]);
continue;
}
if (q < 0 && p > 0)
continue;
if (q > 0 && p < 0)
{
num++;
continue;
}
if (q > 0)
t[++tail] = make_pair(ceil(p / q), true);
else
t[++tail] = make_pair(floor(p / q), false);
}
sort(t + 1, t + tail + 1);
for (int i = 1; i <= tail; i++)
if (!t[i].ps)
num++;
for (int i = 1; i <= tail; i++)
{
int j = i, cnt = 0;
while (t[j + 1].pf == t[i].pf && j + 1 <= tail)
j++;
for (int k = i; k <= j; k++)
if (t[k].ps)
num++;
else
cnt++;
if (num > ans && t[i].pf > 0 && t[i].pf <= y)
ans = num, an[1] = x, an[2] = y, an[3] = t[i].pf;
i = j, num -= cnt;
}
return;
}
signed main()
{
n=rd;
for(int i=1;i<=n;i++){
a[i]=rd;
b[i]=rd;
c[i]=rd;
}
an[1]=an[2]=an[3]=1;
for(int i=1;i<=1000;i++){
for(int j=1;j<=i;j++){
check(i,j);
}
}
cout<<an[1]<<' '<<an[2]<<' '<<an[3];
}