江西竟然还有省选, 而且还是可怜题, 实在是有点可怕
这道题还是比较清真的, 大概是最简单的可怜题?
首先看到最大值最小, 就很容易想到了二分答案
对于一个二分出来的答案 \(mid\), 去把原数列扫一遍就可以得到每一个位置至少要被覆盖几次
现在的问题变成了从 \(m\) 个区间里选择最少的区间, 使得每一个位置都至少被覆盖给定的次数
现在就变成一个贪心问题了
先把所有区间按照左端点排好序, 之后开一根扫描线扫过去, 扫的过程中开一个堆, 用来存储所有被扫描线扫到过左端点的区间
假如我们扫描线扫到一个位置 \(i\), 且 \(i\) 之前的位置都已经被覆盖了, 那么显然这个时候我们需要从堆里找到之前的那些能覆盖到 \(i\) 的区间来覆盖掉 \(i\), 那么自然是优先选择那些右端点更靠右的区间, 它们能覆盖到更多的点
同时覆盖的过程中需要一个区间加, 单点查的数据结构, 自然选择树状数组了
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<queue>
- #include<cmath>
- #include<algorithm>
- #define LL long long
- #define lowbit(x) ((x)&(-x))
- #define re register
- #define maxn 100005
- #define mp std::make_pair
- #define min(a,b) ((a)<(b)?(a):(b))
- #define max(a,b) ((a)>(b)?(a):(b))
- int a[maxn],c[maxn];
- struct Seg
- {
- int l,r;
- }b[maxn];
- int n,m,K,D,T;
- int pre[maxn],d[maxn];
- inline int read()
- {
- char c=getchar();
- int x=0;
- while(c<'0'||c>'9') c=getchar();
- while(c>='0'&&c<='9')
- x=(x<<3)+(x<<1)+c-48,c=getchar();
- return x;
- }
- inline int cmp(Seg A,Seg B)
- {
- return A.l<B.l;
- }
- inline void add(int x,int val)
- {
- for(re int i=x;i<=n;i+=lowbit(i)) c[i]+=val;
- }
- inline int ask(int x)
- {
- int now=0;
- for(re int i=x;i;i-=lowbit(i)) now+=c[i];
- return now;
- }
- typedef std::pair<int,int> pii;
- std::priority_queue<pii> q;
- inline int check(int x)
- {
- memset(d,0,sizeof(d));
- for(re int i=1;i<=n;i++)
- {
- if(a[i]<x) d[i]=ceil(double(x-a[i])/double(D));
- if(d[i]>pre[i]) return 0;
- }
- memset(c,0,sizeof(c));
- while(!q.empty()) q.pop();
- int now=1,tot=0;
- for(re int i=1;i<=n;i++)
- {
- while(b[now].l==i) q.push(mp(b[now].r,b[now].l)),now++;
- if(!d[i]) continue;
- int cnt=ask(i);
- if(cnt>=d[i]) continue;
- while(!q.empty())
- {
- pii mid=q.top();
- q.pop();
- if(mid.first>=i) add(mid.second,1),add(mid.first+1,-1),cnt++,tot++;
- if(cnt==d[i]) break;
- }
- if(cnt<d[i]) return 0;
- }
- return tot<=K;
- }
- int main()
- {
- T=read();
- while(T--)
- {
- n=read(),m=read(),K=read(),D=read();
- memset(pre,0,sizeof(pre)),memset(b,0,sizeof(b));
- for(re int i=1;i<=n;i++) a[i]=read();
- for(re int i=1;i<=m;i++) b[i].l=read(),b[i].r=read(),pre[b[i].l]++,pre[b[i].r+1]--;
- for(re int i=1;i<=n;i++) pre[i]+=pre[i-1];
- std::sort(b+1,b+m+1,cmp);
- int L=999999999,R;
- for(re int i=1;i<=n;i++)
- L=min(L,a[i]);
- R=L+D*K;
- int ans=0;
- while(L<=R)
- {
- int mid=L+R>>1;
- if(check(mid)) ans=mid,L=mid+1;
- else R=mid-1;
- }
- printf("%d\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2905167.html