NC21680. Campaign

描述

输入描述

第一行输入一个T(T≤50000)，表示T组数据。

对于每组数据：
输入一个正整数n(1≤n≤10^9)表示需要分配的兵力总人口。
接下来7行，每行两个正整数L,R(1≤L≤R≤10^9),分别表示该基地够抵挡异虫攻击的最小兵力需求与该基地的人口上限。

输出描述

对于每组数据，输出tokitsukaze最多能够留下几个基地，每组数据占一行。

示例1

输入:

4
50
1 1
1 1
1 1
1 1
1 1
1 1
1 1
50
1 1
20 30
20 30
20 30
1 1
20 30
20 30
70
19 19
10 10
10 10
10 10
10 10
10 10
1 1
2
1 1
3 3
3 3
3 3
3 3
3 3
3 3

输出:

0
4
7
0

说明:

第一个样例，无论tokitsukaze怎么取舍，都不能满足条件。在这种特殊情况下你应该输出0。

第二个样例，tokitsukaze选择第一个第二个第三个和第五个基地，分别分配1,20,28,1的兵力即可满足既能完全分配兵力，同时这4个基地既能防御异虫的攻击，也不超过每个基地的人口上限。

第三个样例，tokitsukaze分别分配19,10,10,10,10,10,1给7个基地就能保证既能完全分配兵力，同时这7个基地既能防御异虫的攻击，也不超过每个基地的人口上限。

第四个样例，tokitsukaze如果只选择1号基地，那么要么无法将所有的兵力完全分配，要么该基地的人口总数将会大于上限，所以任务会直接失败，而如果选择其他基地，那么由于不能达到防御的最小下界。所以也会导致任务失败。不论怎么取舍任务都会失败，所以这种情况下应该输出0。

原站题解

#include<cstdio>
#include<iostream>
using namespace std;
int minn[8],maxn[8];
int main()
{
	int n,t,i,j,k;
	cin>>t;
	for(i=1;i<=t;i++)
	{
		int res=0;
		cin>>n;
		for(j=1;j<=7;j++)
		cin>>minn[j]>>maxn[j];
		for(j=0;j<1<<7;j++)
		{
			int l=0,r=0,count=0;
			for(k=1;k<=7;k++)
			if((1<<(k-1))&j)
			l+=minn[k],r+=maxn[k],count++;
			if(l<=n&&n<=r)
			res=max(res,count);
		}
		cout<<res<<endl;
	}
	return 0;
}