题目链接:https://ac.nowcoder.com/acm/contest/303/D
一共就7个堡垒,问最多可以保留多少个堡垒,所以直接就是二进制枚举就好了,在枚举的过程中要对上下界进行判断。
AC代码:
#include <bits/stdc++.h>
#define maxn 15
#define ll long long
using namespace std;
struct Node{
ll x,y;
}Edge[maxn];
int T,n;
int main()
{
scanf("%d",&T);
while(T--){
scanf("%d",&n);
ll sum = 0;
for(int i=0;i<7;i++){
scanf("%lld%lld",&Edge[i].x,&Edge[i].y);
sum += Edge[i].y;
}
if(sum < n){
puts("0");
continue;
}
ll ans = 0;
for(int i=0;i<(1<<7);i++){
ll a = 0, b = 0, cnt = 0;
for(int j=0;j<7;j++){
if(i & (1 << j)) a += Edge[j].x, b += Edge[j].y, cnt ++;
}
if(a <= n && n <= b) ans = max(ans, cnt);
}
printf("%lld\n", ans);
}
return 0;
}