A27704. 连接(connect)
填空题
中等
知识点
题目描述
连接(connect)
题目描述
N个钢管，各有各的长度，现在想尽可能焊接成一 根长度为L的旗杆，当然有可能不能正好拼接出这个长度，但是要求尽可能接近这个长度，长一点或短一点也是可以， 请你找出最好的方案。
输入格式
第一行两个整数， N和L。
第二行N个整数，表示N个钢管的长度。
输出格式
一个整数，为最佳拼接的长度同期望旗杆长度的差值的绝对值。
输入输出样列
输入样例1
5 16
3 1 3 5 6
输出样例1
1
说明
数据范围：N<=20
参考答案
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i <= b; i ++ )
#define DOR(i, a, b) for(int i = b; i >= a; i -- )
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 50;
int n, L, res = INT_MAX, a[N];
void dfs (int dep, int s) {
if (dep > n) {
res = min (res, abs (s - L));
return;
}
dfs (dep + 1, s + a[dep]);
dfs (dep + 1, s);
return;
}
int main () {
cin >> n >> L;
for (int i = 1; i <= n; i ++ ) {
cin >> a[i];
} dfs (1, 0), cout << res;
return 0;
}
上一题
下一题