exgcd
题意
给 \(n\;(n<=3*10^5)\) 个菜，每个菜可以加红辣椒或黑辣椒，分别可以获得 \(c[i],d[i]\) 分；
有 \(m\;(m<=3*10^5)\) 个商店，第 i 个商店包含 \(x_i,y_i\), 表示只打包卖红辣椒 \(a\) 个，黑辣椒 \(b\) 个，即必须有 \(x,y>=0\), 且 \(a*x+b*y=n\)
求若分别去这 \(m\) 个商店买辣椒，分别最多能获得多少分
思路
- 假设全部加黑辣椒，求出当前的答案 \(ans=\sum d[i]\) （不用管是否满足有解）
- 令 \(e[i]=c[i]-d[i]\), 从大到小排序，求出前缀和 \(s[i]\)，若能加 k 个红辣椒，则就取前 k 个
- 用 exgcd 解出一组解 \(x_0,y_0\), 且 \(x_0\) 为最小非负整数解，此时若 \(y_0<0\) 则返回 -1
- 令 \(d=\gcd(a,b)\), 通解为 \(x=x_0+t*\frac bd\), 并找出满足 \(y>=0\) 的最大的 \(x_{mx}\)
- 由于 \(s[i]\) 是单峰的，三分即可
- 也可以找到峰，求峰两侧的 x 对应的最大值即可（详细见代码）
代码
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
typedef pair<int, int> PII;
const int N = 3e5 + 10;
int n;
ll c[N], s[N];
ll ans;
int idx;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll xx, yy;
ll d = exgcd(b, a % b, xx, yy);
x = yy, y = xx - a / b * yy;
return d;
}
ll solve(ll a, ll b)
{
ll x, y;
ll d = exgcd(a, b, x, y);
if (n % d)
return -1;
x *= n / d, y *= n / d;
ll bb = b / d;
x %= bb;
if (x < 0)
x += bb;
y = (n - x * a) / b;
if (y < 0)
return -1;
int l = x, r = (n - l * a) / (bb * a) * bb + l;
if (l * a >= idx)
return s[l*a] + ans;
if (r * a <= idx)
return s[r*a] + ans;
int lim = (idx - l * a) / (bb * a) * bb + l;
return max(s[lim * a], s[(lim + bb) * a]) + ans;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
int x, y;
cin >> x >> y;
c[i] = x - y;
ans += y;
}
sort(c + 1, c + n + 1, greater<ll>());
for (int i = 1; i <= n; i++)
{
s[i] = s[i-1] + c[i];
if (c[i] >= 0)
idx = i;
}
int q;
cin >> q;
while(q--)
{
int a, b;
cin >> a >> b;
cout << solve(a, b) << endl;
}
return 0;
}