题解 | 小红的优惠券

直接暴力求解，比较满足条件的代金券哪个更优
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int min_n=n;
for(int i=1;i<=m;i++){
    int a,b;
    cin>>a>>b;
    if(a<=n){
        min_n=min(min_n,n-b);
    }
}

cout<<min_n;
    return 0;
}
如果是每一类的代金券只允许用一张，就是说可以无限的用代金券，但是每类只有一张
那么就需要用到二进制枚举 思路：有效到大给满足需求的代金券排序然后筛选出符合要求的
进行二进制枚举，如果在内层循环不符合要求直接剪枝，因为是升序排列前面的不符合要求后面的
一定不符合要求
#include <bits/stdc++.h>
using namespace std;
struct solve{
	int a,b;
}t[105];
bool cmp(solve x,solve y){
	return x.a<y.a;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>t[i].a>>t[i].b;
	sort(t+1,t+1+m,cmp);
	int cnt=0;
	for(int i=1;i<=m;i++){//去掉无法使用的代金券
		if(t[i].a<=n)cnt++;
		else
			break;
	}
	int min_n=n;
	int init_n=n;//保存第一次的n值方便每个循环重置
	for(int mask=0;mask<(1<<cnt);mask++){
		n=init_n;
		bool flag=true;
		for(int i=0;i<cnt;i++){
			if(mask&(1<<i)){
				if(t[i+1].a<=n){
					n-=t[i+1].b;
					if(n<0){
						min_n=0;
						cout<<min_n;
					return 0;
					}
				}
				else{flag=false;
					break;}//剪枝因为是从小到大排的所以前面的不满足后面的肯定不满足
			}
			
		}if(flag)
			min_n=min(min_n,n);
	}
	cout<<min_n;
	return 0;
}