【CF618F】Double Knapsack

这个题目甚是神仙啊QAQ。
假设a数组算到最后总和比b大,我们现在考虑对于每一个i,找出最大的ta满足sa_i>=sb_{ta},其中saa数组的前缀和,sbb数组的前缀和。
这个不等式可以写成0 \leq sa_i – sb_{ta} < n,因为只要大于等于n我们就可以继续向前移动ta
我们从0开始统计这个sa_i – sb_{ta} 的值,那么根据鸽巢原理,一共n+1个数字分配在n个笼子里,至少有两对是相等的,也就说不存在无解的情况。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 1e6 + 10;

int n, lx;

lo sa[ms], sb[ms];

struct in
{
    int x, y;
}pos[ms];

int main()
{
    re(n);
    for(ri i = 1; i <= n; i ++)
        re(sa[i]), sa[i] += sa[i - 1];
    for(ri i = 1; i <= n; i ++)
        re(sb[i]), sb[i] += sb[i - 1];
    for(ri i = 0; i <= n; i ++)
        pos[i] = (in){-1, -1};
    bool f = 0;
    if(sa[n] < sb[n])
        swap(sa, sb), f = 1;
    ri i, ta = 0; lo v;
    for(i = 0; i <= n; i ++)
    {
        while(sa[i] >= sb[ta + 1] && ta + 1 <= n)
            ta ++;
        v = sa[i] - sb[ta];
        //cout << i << ' ' << ta << ' ' << v << '\n';
        if(pos[v].x == -1)
            pos[v] = (in){i, ta};
        else
            break;
    }
    if(f)
        swap(sa, sb), swap(i, ta), swap(pos[v].x, pos[v].y);
    printf("%d\n", i - pos[v].x);
    for(ri j = pos[v].x + 1; j <= i; j ++)
        printf("%d ", j);
    printf("\n");
    printf("%d\n", ta - pos[v].y);
    for(ri j = pos[v].y + 1; j <= ta; j ++)
        printf("%d ", j);
    system("pause");
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注