hdu contest day1 1002 Assignment

本文主要是介绍hdu contest day1 1002 Assignment，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1002&cid=589

思路：对于每个人，向右二分判断能组成group最远的人，用ST表维护最大最小值，判断时只要看最大最小只差是否小于k即可

CYY的代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int64;
const double eps=1e-7;
const int maxn=100015,maxk=20;
int n,m,k,a[maxn];int64 ans;
int bin[maxk],fmx[maxk][maxn],fmn[maxk][maxn];
void read(int &x){char ch;for (ch=getchar();!isdigit(ch);ch=getchar());for (x=0;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
}
void init(){read(n);read(m);for (int i=1;i<=n;++i) read(a[i]);
}
void prepare(){k=floor(log2(n)+eps);for (int i=1;i<=n;++i) fmx[0][i]=fmn[0][i]=a[i];for (int i=1;i<=k;++i)for (int j=bin[i];j<=n;++j){fmx[i][j]=max(fmx[i-1][j],fmx[i-1][j-bin[i-1]]);fmn[i][j]=min(fmn[i-1][j],fmn[i-1][j-bin[i-1]]);}
}
int qmax(int l,int r){int q=floor(log2(r-l+1)+eps);return max(fmx[q][r],fmx[q][l+bin[q]-1]);
}
int qmin(int l,int r){int q=floor(log2(r-l+1)+eps);return min(fmn[q][r],fmn[q][l+bin[q]-1]);
}
int query(int a,int b){int l=a,r=b,res;while (l<=r){int mid=(l+r)>>1;if (qmax(mid,b)-qmin(mid,b)<m) r=(res=mid)-1;else l=mid+1;}return res;
}
void work(){prepare();ans=0;for (int i=1;i<=n;++i) ans+=(i-query(1,i)+1);printf("%I64d\n",ans);
}
int main(){int cases;scanf("%d",&cases);bin[0]=1;for (int i=1;i<maxk;++i) bin[i]=bin[i-1]<<1;while (cases--){init();work();}return 0;
}

这篇关于hdu contest day1 1002 Assignment的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---