本文共 3709 字，大约阅读时间需要 12 分钟。
点击打开链接
1、题目：
热烈庆祝ACM协会获山东理工大学明星社团!pingqing(pingqing)收件箱(0)注销 选美大赛Time Limit: 1000MS Memory limit: 65536K 题目描述 有n个模特参加选美大赛，各个比基尼选手都已经按照编号站在了评委面前，展现自我魅力与个性，等待脱颖而出！ 而评委浪子，收录了每个参赛选手的身高和三围！！众所周知，浪子是个搞Acmer的，他总是对比赛外的一些东西有自己变态的想法！看到身高这一项数据，他就YY着是否能够求 出一系列最长区间（1个或多个）并保证满足：区间内最高的美女与最矮的美女的高度差不超过k！输入输入包含若干组测试数据：n,k(1<=n<=10^5,0<=k<=10^6); 对应每个美女的高度为 hi(1<=hi<=10^6)输出对于每组测试数据,输出最长区间长度以及个数； 并把每个区间输出出来！！（具体参考测试数据）示例输入3 314 12 102 010 10示例输出2 21 22 32 11 2
2、第一遍简单模拟ac的代码：
#include #include int a[1000015];struct node{ int s; int e; int len;} b[1000015];int c[1000015];int u[1000015];int main(){ int n,k; while(scanf("%d%d",&n,&k)!=EOF) { for(int i=1; i<=n; i++) { b[i].len=0; b[i].s=0; b[i].e=0; c[i]=0; u[i]=0; } int max=-1; int max1=-1; int min=999999; int d; for(int i=1; i<=n; i++) { scanf("%d",&a[i]); } int l=1,m=1; for(int j=1; j<=n; j++) { for(int i=j; i<=n; i++) { if(a[i]>max) max=a[i]; if(a[i] k)||((max-min<=k)&&(i==n))) { if(max-min<=k&&i==n) { b[l].len=i-j+1; b[l].s=j; b[l].e=i; } else { b[l].len=i-j; b[l].s=j; b[l].e=i-1; } c[b[l].len]++; if(b[l].len>=max1) { max1=b[l].len; u[m++]=l; } l++; min=99999; max=-1; break; } } } if(max1==1) { printf("1 %d\n",n); for(int i=1; i<=n; i++) printf("%d %d\n",i,i); } else { printf("%d %d\n",max1,c[max1]); for(int p=1; p
2、赛后线段树写的ac的代码：
#include #include using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define max1 0x7fffffffint ma[400005],mi[400005],b[100005],c[100005];int ql[100005],qr[100005];int max(int a,int b){ if(a>b) return a; else return b;}int min(int a,int b){ if(a>b) return b; else return a;}void build(int l,int r,int rt){ int t; if(l==r) { scanf("%d",&t); ma[rt]=mi[rt]=t; return ;//зЂвт } int m=(l+r)>>1; build(lson); build(rson); ma[rt]=max(ma[rt<<1],ma[rt<<1|1]); mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);//}int queryma(int L,int R,int l,int r,int rt){ if(L<=l&&R>=r) return ma[rt]; int ret=0; int m=(l+r)>>1;// if(L<=m) ret=max(ret,queryma(L,R,lson)); if(R>m) ret=max(ret,queryma(L,R,rson)); return ret;}int querymi(int L,int R,int l,int r,int rt){ if(L<=l&&R>=r) return mi[rt]; int m=(l+r)>>1,ret=max1;//错在ret赋值太小 if(L<=m) ret=min(ret,querymi(L,R,lson)); if(R>m) ret=min(ret,querymi(L,R,rson)); return ret;}int main(){ int n,k,t,ans,i,j; while(scanf("%d%d",&n,&k)!=EOF) { build(1,n,1); ans=t=0; for(i=j=1; j<=n; ++i) { if(j ans) { ans=j-i; ql[0]=i; qr[0]=j-1; t=1; } else if(j-i==ans) { ql[t]=i; qr[t++]=j-1; } } printf("%d %d\n",ans,t); for(i=0; i
转载地址：http://mycdi.baihongyu.com/