Algoogle

Algorithm for Programming Contest

PKU 3628 Bookshelf 2

Category: PKU Tag: dfs

Bookshelf 2

問題概要


解法


N<=20なので全探索すればよい

####


(3628.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

int N, B;
int H[20010];
int ans;

void dfs(int i, int sum){
    if(sum >= B) {
        ans = min(ans, sum);
        return;
    }
    if(i == N) return;
    dfs(i+1, sum);
    dfs(i+1, sum+H[i]);
}

int main(){
    scanf("%d%d", &N, &B);
    for(int i = 0; i < N; i++)
        scanf("%d", H+i);
    sort(H, H+N);
    ans = 1e9;
    dfs(0, 0);
    printf("%d\n", ans-B);
    return 0;
}

Comments