申请网站做自己的产品,网站建设后台怎么修改,怎样才能把网站宣传做的更好,网站页面字体设置题干#xff1a;
星际争霸(StarCraft)单人战役模式中有很多供人游玩的任务关卡。
tokitsukaze新开始了一关单人战役模式下的任务。在这场战役中#xff0c;你要作为指挥官指挥克鲁普星区的艾伦人类(Terran)来防御人类的敌人——邪恶异虫(Zerg)的袭击。
这一次#xff0c;…题干
星际争霸(StarCraft)单人战役模式中有很多供人游玩的任务关卡。
tokitsukaze新开始了一关单人战役模式下的任务。在这场战役中你要作为指挥官指挥克鲁普星区的艾伦人类(Terran)来防御人类的敌人——邪恶异虫(Zerg)的袭击。
这一次作为指挥官你的任务目标是尽可能多的保全人类方所拥有的7个基地。你在这次任务中拥有n个人口单位的兵力。为了防御异虫的攻击每个基地都有一个能够抵挡异虫攻击的最小兵力需求L[i]同时每个基地因为有固定的人口上限分配给该基地的兵力也不得大于上限R[i]。
你需要在任务一开始就为这7个基地做好兵力分配每个兵都应该分配给一个基地即不应该有空闲兵力。如果任何一个基地被异虫攻破(分配的兵力大于0且小于最小兵力需求导致兵力白白葬送牺牲)或者某个基地的人口超过了人口上限兵力大于R[i]任务都会直接失败。
为了避免任务失败tokitsukaze决定从一开始就放弃一些基地(即不对这些基地派出兵力)。
请问保证任务成功的条件下tokitsukaze最多留下多少个基地特别的如果任务失败这种情况下请输出0不含引号。
由于tokitsukaze的星际操作十分流弊你可以认为如果能够至少能够保留一个基地任务就一定能够成功。
输入描述:
第一行输入一个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。
解题报告 就是个枚举答案实在不行就7层循环、、然后维护一个可行的l,r当可行的l,r包含了输入的数的时候就是满足条件的然后从所有答案中选出最大的就行。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
ll n;
ll low[15],up[15];
bool fit(ll i,int j) {if((ij)1) return 1;else return 0 ;
}
int get(ll i) {int cnt 0;while(i) {if(i1) cnt;i1; }return cnt;
}
int main()
{int t;cint;while(t--) {scanf(%lld,n);int ans 0;for(int i 1; i7; i) {scanf(%lld%lld,lowi,upi);}ll minn 0,maxx 0;for(ll i 0; i(17); i) {minnmaxx0;for(int j 1; j7; j) {if(fit(i,j-1)) minnlow[j],maxxup[j];}if(minnn maxxn) ans max(ans,get(i));}printf(%d\n,ans);}return 0 ;}%%%Qls
#includebits/stdc.h
using namespace std;typedef long long ll;ll l[15],r[15];int main()
{int T;scanf(%d,T);while(T--){int n;scanf(%d,n);for(int i0;i7;i)scanf(%lld%lld,l[i],r[i]);int res0;for(int i0;i(17);i){ll mi0,mx0;for(int j0;j7;j)if(ij1)mil[j],mxr[j];if(min nmx)resmax(res,__builtin_popcount(i));}printf(%d\n,res);}return 0;
}
