个数 += -1 content -s esp 一个 sig
题意:给 T 足数据,然后每组一个 n 和 k,表示 n 个数,k 表示最大同意的能力差,接下来 n 个数表示 n 个人的能力,求能力差在 k 之内的区间有几个
分析:维护一个区间的最大值和最小值,使得他们的差小于 k,于是採用单调队列
普通单调队列做法:
二分单调队列做法:
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cmath>
- using namespace std;
- const int maxn = 1e6+5;
- int a[maxn];
- struct node{
- int index;
- int v;
- }qd[maxn];
- node qx[maxn];
- int main()
- {
- int t;
- scanf("%d",&t);
- while(t--)
- {
- int n,k;
- scanf("%d%d",&n,&k);
- for(int i=1;i<=n;i++){
- scanf("%d",&a[i]);
- }
- int st1,st2,ed1,ed2;
- st1=st2=ed1=ed2=1;
- long long sum=0;
- int j=1;
- for(int i=1;i<=n&&j<=n;i++){
- if(i==1){
- qd[1].index=qx[1].index=1;
- qd[1].v=qx[1].v=a[1];
- }
- else{
- while(st1<=ed1){ //单调队列维护最大值
- if(qd[ed1].v<=a[i]) ed1--; //比a[i]小的并且下标比i小的出队列
- else break;
- }
- qd[++ed1].v=a[i]; //a[i]入队列
- qd[ed1].index=i;
- while(st2<=ed2){ //单调队列维护最小值
- if(qx[ed2].v>=a[i]) ed2--; //比a[i]大并且下标比i小的出队列
- else break;
- }
- qx[++ed2].v=a[i]; //a[i]入队列
- qx[ed2].index=i;
- while(qd[st1].v-qx[st2].v>=k&&st1<=ed1&&st2<=ed2) //计数
- {
- if(qd[st1].index==j) st1++;
- if(qx[st2].index==j) st2++;
- sum+=(i-j);
- j++;
- }
- }
- }
- while(j<=n) {
- sum+=(n-j+1);
- j++;
- }
- printf("%I64d\n",sum);
- }
- }
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cmath>
- using namespace std;
- const int maxn = 1e6+5;
- int a[maxn];
- struct node{
- int index;
- int v;
- }qd[maxn];
- node qx[maxn];
- int maxc(int l,int r,int d){ //二分找出d入队列的为止
- while(l<=r){
- int mid=(l+r)/2;
- if(qd[mid].v==d) return mid;
- else if(qd[mid].v>d) l=mid+1;
- else r=mid-1;
- }
- return l;
- }
- int minc(int l,int r,int d){ //二分找出d入队列的为止
- while(l<=r){
- int mid=(l+r)/2;
- if(qx[mid].v==d) return mid;
- else if(qx[mid].v<d) l=mid+1;
- else r=mid-1;
- }
- return l;
- }
- int main()
- {
- int t;
- scanf("%d",&t);
- while(t--)
- {
- int n,k;
- scanf("%d%d",&n,&k);
- for(int i=1;i<=n;i++){
- scanf("%d",&a[i]);
- }
- int st1,st2,ed1,ed2;
- st1=st2=ed1=ed2=1;
- long long sum=0;
- int j=1;
- for(int i=1;i<=n&&j<=n;i++){
- if(i==1){
- qd[1].index=1;
- qd[1].v=a[1];
- qx[1].index=1;
- qx[1].v=a[1];
- }
- else{
- ed1=maxc(st1,ed1,a[i]); //二分找出d入队列的为止,维护最大值
- qd[ed1].v=a[i];
- qd[ed1].index=i;
- ed2=minc(st2,ed2,a[i]); //二分找出d入队列的为止,维护最小值
- qx[ed2].v=a[i];
- qx[ed2].index=i;
- while(qd[st1].v-qx[st2].v>=k&&st1<=ed1&&st2<=ed2)//计数
- {
- if(qd[st1].index==j) st1++;
- if(qx[st2].index==j) st2++;
- sum+=(i-j);
- j++;
- }
- }
- }
- while(j<=n) {
- sum+=(n-j+1);
- j++;
- }
- printf("%I64d\n",sum);
- }
- }
HDU 5289 Assignment(单调队列)
来源: http://www.bubuko.com/infodetail-2048503.html