HDU 5289——Assignment——————【RMQ+最適化解】
4022 ワード
Assignment
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 902 Accepted Submission(s): 441
Problem Description
Tom owns a company and he is the boss. There are n staffs which are numbered from 1 to n in this company, and every staff has a ability. Now, Tom is going to assign a special task to some staffs who were in the same group. In a group, the difference of the ability of any two staff is less than k, and their numbers are continuous. Tom want to know the number of groups like this.
Input
In the first line a number T indicates the number of test cases. Then for each case the first line contain 2 numbers n, k (1<=n<=100000, 0
Output
For each test,output the number of groups.
Sample Input
2 4 2 3 1 2 4 10 5 0 3 4 5 2 1 6 7 8 9
Sample Output
5 28
Hint
First Sample, the satisfied groups include:[1,1]、[2,2]、[3,3]、[4,4] 、[2,3]
t組のテストデータをあげます.各グループにはn,kがある.シーケンス長がnであることを示し,区間内の任意の要素の差がk未満であることを満たす連続する区間がどれだけあるかを求める.
解題構想:現在i,jで左右区間位置をそれぞれ表す.次に左から右に拡張し、拡張する要素と区間内の任意の要素との差がkより小さい場合、res++、区間は右に長さを拡張します.エレメントAjに遭遇し、区間内のエレメントと衝突するまで、私はこのAjを右に拡張することを停止します.そして、元の区間[i,j-1]の左区間を右に1つ移動させます.左区間を右に移動すると、この区間内の該当区間の個数は必ず先ほどの[i,j-1]という区間より1つ少ないので、res--.そしてこの時点で前回衝突した位置jを拡張し続け、現在の区間がAjと衝突しないかどうかを見る.そしてずっと繰り返し操作します.簡単にまとめると、右区間が拡張できれば、拡張します.拡張はできません.左区間を右に移動させ、現在の区間が右区間を右に拡張できるかどうかを見ます.
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 902 Accepted Submission(s): 441
Problem Description
Tom owns a company and he is the boss. There are n staffs which are numbered from 1 to n in this company, and every staff has a ability. Now, Tom is going to assign a special task to some staffs who were in the same group. In a group, the difference of the ability of any two staff is less than k, and their numbers are continuous. Tom want to know the number of groups like this.
Input
In the first line a number T indicates the number of test cases. Then for each case the first line contain 2 numbers n, k (1<=n<=100000, 0
Output
For each test,output the number of groups.
Sample Input
2 4 2 3 1 2 4 10 5 0 3 4 5 2 1 6 7 8 9
Sample Output
5 28
Hint
First Sample, the satisfied groups include:[1,1]、[2,2]、[3,3]、[4,4] 、[2,3]
t組のテストデータをあげます.各グループにはn,kがある.シーケンス長がnであることを示し,区間内の任意の要素の差がk未満であることを満たす連続する区間がどれだけあるかを求める.
解題構想:現在i,jで左右区間位置をそれぞれ表す.次に左から右に拡張し、拡張する要素と区間内の任意の要素との差がkより小さい場合、res++、区間は右に長さを拡張します.エレメントAjに遭遇し、区間内のエレメントと衝突するまで、私はこのAjを右に拡張することを停止します.そして、元の区間[i,j-1]の左区間を右に1つ移動させます.左区間を右に移動すると、この区間内の該当区間の個数は必ず先ほどの[i,j-1]という区間より1つ少ないので、res--.そしてこの時点で前回衝突した位置jを拡張し続け、現在の区間がAjと衝突しないかどうかを見る.そしてずっと繰り返し操作します.簡単にまとめると、右区間が拡張できれば、拡張します.拡張はできません.左区間を右に移動させ、現在の区間が右区間を右に拡張できるかどうかを見ます.
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define INT long long
const int maxn=1e5+20;
int d[maxn][50];
int dp[maxn][50];
int A[maxn];
int Abs(int x){
return x<0? -x:x;
}
void RMQ_init(int n){//RMQ i，j 。
for(int i=0;i<n;i++){
d[i][0]=A[i];
dp[i][0]=A[i];
}
for(int j=1;(1<<j)<=n;j++){
for(int i=0;i+(1<<j)-1<n;i++){
d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
}
}
int RMQ(int L,int R,int typ){
int k=0;
while((1<<(k+1)<=R-L+1))
k++;
if(typ==0)
return min(d[L][k],d[R-(1<<k)+1][k]);
else
return max(dp[L][k],dp[R-(1<<k)+1][k]);
}
int main(){
int t,i,j,k,n,tmp,ret,itvlav,itvliv,sum,flag;
INT res,ans;
scanf("%d",&t);
while(t--){
memset(dp,0,sizeof(dp));
memset(d,0,sizeof(d));
memset(A,0,sizeof(A));
scanf("%d%d",&n,&k);
for(i=0;i<n;i++){
scanf("%d",&A[i]);
}
RMQ_init(n);
tmp=0,res=0,sum=0;
itvlav=itvliv=A[0];
for(i=0;i<n;i++){
flag=0;
for(j=tmp;j<n;j++){
if(Abs(itvlav-A[j])<k&&Abs(itvliv-A[j])<k){//
tmp=j+1;
itvlav=RMQ(i,j,1);
itvliv=RMQ(i,j,0);
res++;
}else{ // ， ，
flag=1;
tmp=j;
itvlav=RMQ(i+1,j-1,1);
itvliv=RMQ(i+1,j-1,0);
break;
}
}
sum+=res;
res--;
if(flag==1){
if(res==0){
itvlav=itvliv=A[tmp];
}
}
}
printf("%lld
",sum);
}
return 0;
}