链接https://codeforces.com/gym/102769/standings
题目大意
有n个学生 每个学生有两个成绩 你可以选择一个为这个学生的最终成绩
设这n个学生的最终成绩中最大的为MAX
问你如何选择 让数量最多的学生最终成绩不低于MAX的百分之P
题目思路
每个学生的两个成绩 ai 和 bi ai >= bi
我们考虑对每个学生划一个区间 代表着让这个学生满足题意的max区间
例如某学生ai = 3 bi =6 P=60
那么对于该学生的满足题意的区间就是 3——3/0.6 6——6/0.6 如下图所示
大家可以思考一下如果max在这个区间里 是否满足题意
要注意/P时向下取整 还要注意两个区间重叠的情况 以及离散化
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ls(int x)
{return x<<1;
}
int rs(int x)
{return x<<1|1;
}
const int maxn=8e5+10;
int T,n,cnt;
ll p;
map<ll ,int >m;
ll num[maxn*2];
struct tc
{ll l1,r1;ll l2,r2;
}e[maxn];
struct tree
{int v,add;
}t[maxn*4];
void pushup(int x)
{t[x].v=max(t[ls(x)].v,t[rs(x)].v);
}
void build(int x,int l,int r)
{t[x].add=0;t[x].v=0;if(l==r){return ;}int mid=(l+r)/2;build(ls(x),l,mid);build(rs(x),mid+1,r);pushup(x);
}
void pushdown(int x,int l,int r)
{if(t[x].add==0)return ;t[ls(x)].v+=t[x].add;t[rs(x)].v+=t[x].add;t[ls(x)].add+=t[x].add;t[rs(x)].add+=t[x].add;t[x].add=0;
}
void updata(int l,int r,int nl,int nr,int x,int k)
{if(nl>=l&&nr<=r){t[x].add+=k;t[x].v+=k;return ;}pushdown(x,nl,nr);int mid=(nl+nr)/2;if(l<=mid)updata(l,r,nl,mid,ls(x),k);if(mid<r)updata(l,r,mid+1,nr,rs(x),k);pushup(x);
}
int query(int l,int r,int nl,int nr,int x)
{if(nl>=l&&nr<=r){return t[x].v;}pushdown(x,nl,nr);int mid=(nl+nr)/2;int tmp=0;if(l<=mid){tmp=max(tmp,query(l,r,nl,mid,ls(x)));}if(r>mid) {tmp=max(tmp,query(l,r,mid+1,nr,rs(x)));}pushup(x);return tmp;
}
void init()
{m.clear();for(int i=0;i<=n;i++){e[i].l1=e[i].l2=e[i].r1=e[i].r2=0;} for(int i=0;i<=cnt;i++)num[i]=0; cnt=0;
}
int main()
{cin>>T;int ct=0;while(T--){scanf("%d %lld",&n,&p);init();ll ai,bi;ll lw=0;for(int i=1;i<=n;i++){scanf("%lld %lld",&ai,&bi);lw=max(lw,bi);int a,b,c,d;if((ai)<=(bi*100)/p){if(m[(ai*100)/p]==0){m[(ai*100)/p]++;num[++cnt]=(ai*100)/p;}if(m[bi]==0){m[bi]++;num[++cnt]=bi;}e[i].r1=(ai*100)/p;e[i].l1=bi;}else {if(m[(bi*100)/p]==0){m[(bi*100)/p]++;num[++cnt]=(bi*100)/p;}if(m[bi]==0){m[bi]++;num[++cnt]=bi;}if(m[(ai*100)/p]==0){m[(ai*100)/p]++;num[++cnt]=(ai*100)/p;}if(m[ai]==0){m[ai]++;num[++cnt]=ai;}e[i].r1=(bi*100)/p;e[i].l1=bi;e[i].r2=(ai*100)/p;e[i].l2=ai;}} if(m[lw]==0){m[lw]++;num[++cnt]=lw;}//cout<<lw<<endl;sort(num+1,num+cnt+1);build(1,1,cnt);for(int i=1;i<=n;i++){e[i].l1=lower_bound(num+1,num+cnt+1,e[i].l1)-num;e[i].r1=lower_bound(num+1,num+cnt+1,e[i].r1)-num;//cout<<e[i].l1<<" "<<e[i].r1<<endl;updata(e[i].l1,e[i].r1,1,cnt,1,1);if(e[i].l2==0)continue;e[i].l2=lower_bound(num+1,num+cnt+1,e[i].l2)-num;e[i].r2=lower_bound(num+1,num+cnt+1,e[i].r2)-num;//cout<<e[i].l2<<" "<<e[i].r2<<endl;updata(e[i].l2,e[i].r2,1,cnt,1,1);}lw=lower_bound(num+1,num+cnt+1,lw)-num;//cout<<lw<<" "<<cnt<<endl;printf("Case #%d: %d\n",++ct,query(lw,cnt,1,cnt,1));}return 0;
}