HDU 5289 Assignment(2015 Multi-University Training Contest 1)
4072 ワード
Assignment
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2976 Accepted Submission(s): 1385
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
Sample Output
Author
FZUACM
Source
2015 Multi-University Training Contest 1
题意:T足のデータをあげて、それから各グループの1つのnとk、nの数を表して、kは最大の许す能力の差を表して、次のnの数はn个人の能力を表して、能力の差を求めてkの内の区间はいくつあります.
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2976 Accepted Submission(s): 1385
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]
Author
FZUACM
Source
2015 Multi-University Training Contest 1
题意:T足のデータをあげて、それから各グループの1つのnとk、nの数を表して、kは最大の许す能力の差を表して、次のnの数はn个人の能力を表して、能力の差を求めてkの内の区间はいくつあります.
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define LL __int64
const int MIN=1e9+10;
const int MAX=0;
const int maxm=1e5+10;
int a[maxm];
int mina[maxm];
int maxa[maxm];
int n,k;
void Init()
{
for(int i=0;i<=maxm;i++)
{
mina[i]=MIN;
maxa[i]=MAX;
}
}
int lowbit(int i)
{
return i&(-i);
}
void add(int i,int v)
{
while(i<=n)
{
mina[i]=min(mina[i],v);
maxa[i]=max(maxa[i],v);
i+=lowbit(i);
}
}
int quertymin(int i)
{
int Min=MIN;
while(i>0)
{
Min=min(Min,mina[i]);
i-=lowbit(i);
}
return Min;
}
int quertymax(int i)
{
int Max=MAX;
while(i>0)
{
Max=max(Max,maxa[i]);
i-=lowbit(i);
}
return Max;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
Init();
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
LL sum=0;
for(int i=n;i>=1;i--)
{
add(i,a[i]);
int low=i;
int high=n;
int p=0;
while(low<=high)
{
int mid=(low+high)>>1;
if(quertymax(mid)-quertymin(mid)<k)
{
p=mid;
low=mid+1;
}
else
{
high=mid-1;
}
}
sum+=p-i+1;
}
printf("%I64d
",sum);
}
return 0;
}