CF1728 ERed-Black Pepper

CF1728ERed-Black Pepper

题目描述

Monocarp is going to host a party for his friends. He prepared $n$ dishes and is about to serve them. First, he has to add some powdered pepper to each of them — otherwise, the dishes will be pretty tasteless.

The $i$-th dish has two values $a_i$ and $b_i$ — its tastiness with red pepper added or black pepper added, respectively. Monocarp won’t add both peppers to any dish, won’t add any pepper multiple times, and won’t leave any dish without the pepper added.

Before adding the pepper, Monocarp should first purchase the said pepper in some shop. There are $m$ shops in his local area. The $j$-th of them has packages of red pepper sufficient for $x_j$ servings and packages of black pepper sufficient for $y_j$ servings.

Monocarp goes to exactly one shop, purchases multiple (possibly, zero) packages of each pepper in such a way that each dish will get the pepper added once, and no pepper is left. More formally, if he purchases $x$ red pepper packages and $y$ black pepper packages, then $x$ and $y$ should be non-negative and $x \cdot x_j + y \cdot y_j$ should be equal to $n$ .

For each shop, determine the maximum total tastiness of the dishes after Monocarp buys pepper packages only in this shop and adds the pepper to the dishes. If it’s impossible to purchase the packages in the said way, print -1.

输入格式

The first line contains a single integer $n$ ( $1 \le n \le 3 \cdot 10^5$ ) — the number of dishes.

The $i$ -th of the next $n$ lines contains two integers $a_i$ and $b_i$ ( $1 \le a_i, b_i \le 10^9$ ) — the tastiness of the $i $-th dish with red pepper added or black pepper added, respectively.

The next line contains a single integer $m $( $1 \le m \le 3 \cdot 10^5$ ) — the number of shops.

The $j$-th of the next $m$ lines contains two integers $x_j$ and $y_j$ ( $1 \le x_j, y_j \le n$ ) — the number of servings the red and the black pepper packages are sufficient for in the $j$ -th shop, respectively.

输出格式

Print $m$ integers. For each shop, print the maximum total tastiness of the dishes after Monocarp buys pepper packages only in this shop and adds the pepper to the dishes. If it’s impossible to purchase the packages so that each dish will get the pepper added once and no pepper is left, print -1.

题目翻译

有n道菜， 对于第i道菜加入一份a佐料有$a[i]$的价值，加入一份b有$b[i]$的价值，每道菜只能加入一份佐料。现在有m个商店，每个商店都按瓶售卖佐料，一个瓶中只能有佐料a或者佐料b，一瓶佐料a有x份，一瓶佐料佐料b有y份，购买的佐料必须完全用完。求分别在每个商店购买佐料能获得价值的最大值，如果不能输出-1。

题目分析

对每个商店一眼就能列出不定方程组$ax+by=n$,如果有解，有 $a*x$ 的通解：$x*a_0+lcm(x,y)*k$,那么可以算出来 $a*x$ 的取值在一个范围，而且间隔都是lcm，那么先预处理出来选择i道菜加入佐料a，n-i道菜加入佐料b的最大价值，可以发现，选择i道菜加入佐料a的价值肯定是个单峰函数，而$a*x$的取值范围也已知，那么可以通过二分求解，或者直接判断在峰两侧的值和取值范围两端的最大值。

代码

#include <bits/stdc++.h>

using ll = long long;

long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, x, y);
    ll t = x;
    x = y;
    y = t - a / b * x;
    return d;
}

void sol() {
    int n;
    std::cin >> n;
    std::vector<int> diff(n);
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        int a, b;
        std::cin >> a >> b;
        diff[i] = a - b;
        sum += b;
    }
    std::sort(diff.begin(), diff.end(), std::greater());
    std::vector<long long> pref(n + 1);
    for (int i = 1; i <= n; ++i)pref[i] = pref[i - 1] + diff[i - 1];
    long long big = std::max_element(pref.begin(), pref.end()) - pref.begin();

    int m;
    std::cin >> m;
    while (m--) {
        int x, y;
        std::cin >> x >> y;

        long long a, b;
        long long g = exgcd(x, y, a, b);
        if (n % g) {
            std::cout << -1 << "\n";
            continue;
        }
        a = a * (n / g) % (y / g);
        if (a < 0) a += y / g;

        if (1LL * x * a > n) {
            std::cout << -1 << "\n";
            continue;
        }

        long long lcm = x * y / g;
        long long lef = x * a;
        long long rig = n - (n - x * a) % lcm;

        long long ans = std::max(pref[lef], pref[rig]);
        if (big >= lef && big <= rig) {
            int l = big - (big - lef) % lcm;
            int r = big + (rig - big) % lcm;
            ans = std::max({ans, pref[l], pref[r]});
        }
        std::cout << ans + sum << "\n";
    }
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
#ifndef LOCAL
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#endif
    sol();
    return 0;
}