[Offer收割]编程练习赛4 A 满减优惠

满减优惠

描述

输入

输出

样例输入

样例输出

题解：

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

#define PU puts("");

#define PI(A) cout<<(A)<<endl

#define SI(N) cin>>(N)

#define SII(N,M) cin>>(N)>>(M)

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

const int MAXN = 20 + 9 ;

int dp[20 * 100 + 5];

int a[MAXN];

int N, X;

bool ok(int u) {

    for(int i = 0; i < N; i++)

        for(int j = u; j >= a[i]; j--)

            dp[j] = max(dp[j], dp[j - a[i]] + a[i]);

    if(dp[u] == u) return 1;

    else return 0;

}

int main() {

    while(SII(N, X)) {

        int sum = 0;

        rep(i, N) SI(a[i]), sum += a[i];

        sort(a, a + N);

        if(sum < X) {

            puts("-1");

            continue;

        }

        int u = X;

        for(; u < sum ; u++) {

            cle(dp, 0);

            if(ok(u)) break;

        }

        PI(u);

    }

    return 0;

}

以下还有一份，是dfs的代码，写起来很简洁，但时间复杂度就有些高了，O(2^20)

代码2：

#include <bits/stdc++.h>

using namespace std;

int min_sum, x;

vector<int> a;

void DFS(int idx, int sum) {

    if(sum >= x) {

        min_sum = min(sum, min_sum);

        return;

    }

    if(idx >= a.size()) {

        return;

    }

    DFS(idx + 1, sum);

    DFS(idx + 1, sum + a[idx]);

}

int main() {

    int n;

    while(scanf("%d %d", &n, &x) != EOF) {

        a.clear();

        int temp, sum = 0;

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

            scanf("%d", &temp);

            a.push_back(temp);

            sum += temp;

        }

        min_sum = sum;

        DFS(0, 0);

        if(min_sum == sum) {

            printf("-1\n");

        } else {

            printf("%d\n", min_sum);

        }

    }

}

再来一份，大神代码，rank1的，用的是非递归版的，也就是枚举所有情况，复杂度O(2^N)，虽然这份跑的时间比上一份还长，但大神做的时候一定是已经想到了这个复杂度，觉对不会TLE，所以才写的，所以还是比较佩服这份

代码3：

#include <bits/stdc++.h>

using namespace std;

#define N 100020

#define M 100200

#define eps 1e-12

#define inf 0x3f3f3f3f

int n, a[N], X;

int main() {

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

    int sum = 0;

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

        scanf("%d", &a[i]);

        sum += a[i];

    }

    if(sum < X) {

        puts("-1");

        return 0;

    }

    int ans = inf;

    for(int s = 1; s < (1 << n); ++s) {

        int t = 0;

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

            if(s >> j & 1) {

                t += a[j];

            }

        }

        if(t >= X) ans = min(ans, t);

    }

    printf("%d\n", ans);

    return 0;

}