板题

给出n个整数,选出若干数,使和恰好为k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//dfs
#include <iostream>
using namespace std;
int arr[1000];
int n,k;
bool dfs(int i,int sum){
if (i == n)
return sum == k;
if (dfs(i + 1,sum))
return true;
if (dfs(i + 1,sum + arr[i]))
return true;
return false;
}

int main() {
cin >> n >> k;
for (int i = 0; i < n; ++i) {
cin >> i[arr];
}
dfs(0,0) == true ? cout << 1 : cout << 0;
return 0;
}

给定几个数,输出最小的无法组成的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//dp
#include <iostream>
#include <algorithm>

using namespace std;

 
int a[1005];
 
int main(){
    int miss = 0;
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
     cin >> i[a];
    sort(a,a+n);
    for(int i = 0; i < n; i++){
        if(i[a] > miss + 1)
         break;
        miss += a[i];
    }
    cout << miss + 1 << endl;
    return 0;
}

给出n段绳子,长度分别为Li.如果从中取出k条长度相同的绳子,每条绳子最长有多长.

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
31
32
33
34
//binary
#include <iostream>
using namespace std;

int N,K;
double Len[10000]
bool isLegal(double l) {
int num = 0;
for (int i = 0; i < N; i++) {
num += (int)(Len[i] / x);
}
return num >= k;
}

void solve() {
double left = 0,right = 1000000;
for(int i = 0; i < 100; i++) {
double mid = (left + right) / 2;
if(isLegal())
left = mid;
else
right = mid;
}
cout << floor(right * 100) / 100 << endl;
}

int main() {
cin >> N >> K;
for (int i = 0; i < N; i++) {
cin >> Len[i];
}
solve();
return 0;
}
script>