C. Jury Marks 思维题

http://codeforces.com/contest/831/problem/C

做的时候想不到，来了个暴力。

对于每个b[i]，枚举每一个a[i]，就有1个可能的情况。

然后用vector存起来，再判断。理论复杂度爆咋，过了综测717ms

正确的思路就是排一个序。

预处理前缀和suma_i，然后就相当于每一个数字只能选一次。从小到大排序。

从大到小排序b_i，枚举每一个suma_i，用b[1]确定一个初始值，然后跑完所有b_i，看看suma_i那里有没有就行了。

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

int a[], b[];

const int maxn = 8e6 + ;

map<int, bool> vis;

vector<int>vc;

int sum[];

bool cmp(int a, int b) {

    return a > b;

}

void work() {

    int n, k;

    scanf("%d%d", &k, &n);

    for (int i = ; i <= k; ++i) {

        scanf("%d", a + i);

        sum[i] = sum[i - ] + a[i];

        vis[sum[i]] = true;

    }

    for (int i = ; i <= n; ++i) {

        scanf("%d", b + i);

    }

    sort(sum + , sum +  + k);

    sort(b + , b +  + n, cmp);

    int ans = ;

    for (int i = ; i <= k; ++i) {

        if (i >  && sum[i] == sum[i - ]) continue;

        int val = b[] - sum[i];

        bool flag = true;

        for (int j = ; j <= n; ++j) {

            if (!vis[b[j] - val]) {

                flag = false;

                break;

            }

        }

        ans += flag;

    }

    cout << ans << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

巴特西

C. Jury Marks 思维题

最新文章

热门文章