CF618F Double Knapsack

· · 题解

博客食用更佳

CF618F Double Knapsack

\texttt{Description}

题面很友好，略。

\texttt{Solution}

看到这种题没什么思路，我首先就输出了 -1，结果 0pts。

于是我大胆猜想，每一个都有解，并且在两个集合中都是一个子段。

尝试证明。

设 suma 表示 a 数组的前缀和，sumb 表示 b 数组的前缀和。

不妨设 suma_n\le sumb_n。

定义 c_i 为 suma_i\ge sumb_j 的最大的 j，显然 0\le c_i\le n。

容易发现，suma_i<sumb_{c_i+1}，即 suma_i<sumb_{c_i}+b_{c_i+1}。

移项得 suma_i-sumb_{c_i}<b_{c_i+1}。

因为 1\le b_{c_i+1}\le n，所以 0\le suma_i-sumb_{c_i}<n，有 n 种可能，而 0\le i\le n，有 n+1 种可能。

根据抽屉原理，可知至少有两个 suma_i-sumb_{c_i} 是相等的，于是就证明了都有解的猜想。

假设 suma_{i1}-sumb_{c_{i1}}=suma_{i2}-sumb_{c_{i2}}，不妨设 i1>i2。

移项可得 suma_{i1}-suma_{i2}=sumb_{c_{i1}}-sumb_{c_{i2}}。

此时一组答案就可以是 a 中的 [i2+1,i1] 和 b 中的 [c_{i2}+1,c_{i1}]，于是证明了答案都是两个集合中的一个子段。

至于如何快速求出每个 c_i，由于 c_i 是单调不下降的，所以弄个指针就行了。

时间复杂度：\mathcal{O}(n)

\texttt{Code}

#include <cstdio>
#include <iostream>

using namespace std;

typedef long long ll;
template <typename T>
inline void Swap (T &x, T &y) {x ^= y ^= x ^= y;}

int a[1000005], b[1000005], c[1000005], id[1000005][2];
ll suma[1000005], sumb[1000005], flag[1000005];

int main () {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), suma[i] = suma[i - 1] + 1ll * a[i];
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i]), sumb[i] = sumb[i - 1] + 1ll * b[i];
    bool isSwap = false;
    if (suma[n] > sumb[n]) {
        isSwap = true;
        for (int i = 1; i <= n; i++)
            Swap(a[i], b[i]), Swap(suma[i], sumb[i]);
    }
    int j = 0, al, ar, bl, br;
    for (int i = 0; i <= n; i++) {
        for (; suma[i] >= sumb[j] && j <= n; j++);
        j--;
        if (flag[suma[i] - sumb[j]]) {
            al = id[suma[i] - sumb[j]][0] + 1;
            ar = i;
            bl = id[suma[i] - sumb[j]][1] + 1;
            br = j;
            break;
        }
        flag[suma[i] - sumb[j]] = true;
        id[suma[i] - sumb[j]][0] = i;
        id[suma[i] - sumb[j]][1] = j;
    }
    if (isSwap)
        Swap(al, bl), Swap(ar, br);
    printf("%d\n", ar - al + 1);
    for (int i = al; i <= ar; i++)
        printf("%d ", i);
    printf("\n%d\n", br - bl + 1);
    for (int i = bl; i <= br; i++)
        printf("%d ", i);
    return 0;
}