T12
2025-01-21 10:48:01
发布于：上海
27阅读
0回复
0点赞
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int ll;
const int MAXN = 1100000;
ll n, t, cnt1, cnt2, ans;//cnt1、cnt2分别表示a、b两个数组中的元素数量
ll num[50], a[MAXN], b[MAXN];//a、b数组分别表示前半段、后半段中所有方案的元素和
void dfs1(int x, ll total) {
if (total > t) {
return;
}
if (x == n / 2 + 1) {
a[++cnt1] = total;
return;
}
dfs1(x + 1, total);
dfs1(x + 1, total + num[x]);
}
void dfs2(int x, ll total) {
if (total > t) {
return;
}
if (x == n + 1) {
b[++cnt2] = total;
return;
}
dfs2(x + 1, total);
dfs2(x + 1, total + num[x]);
}
int main() {
cin >> n >> t;
for (int i = 1; i <= n; i++) {
cin >> num[i];
}
dfs1(1, 0);
dfs2(n / 2 + 1, 0);
sort(a + 1, a + 1 + cnt1);
sort(b + 1, b + 1 + cnt2);
for (int i = 1; i <= cnt1; i++) {
int idx = upper_bound(b + 1, b + 1 + cnt2, t - a[i]) - b;//找到第一个大于T-a[i]的位置
ans = max(ans, a[i] + b[idx - 1]);//与最后一个小于等于T-a[i]的数值合并
}
cout << ans;
return 0;
}
有帮助，赞一个