1810.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:1810  User Id:fzk 
Memory:80K  Time:765MS
Language:C++  Result:Accepted

Source 

#include"iostream.h"
#include"algorithm"
using std::sort;

int s[1001],N,K,M;
long d[10000];


int max()
{int i,k=M;
for(i=M+1;i<=N;i++)if(s[k]<=s[i])k=i;
return k;
}

void find()
{int i,j,k,h,down,up,x=N,y=N,best=0;
	
	for(i=N,j=0,h=0;i>=M;i--)
	{while(h<j&&d[h]%2000>i)
		{down=d[h]/2000;up=down+M-1<N?down+M-1:N;
		for(k=down;k<=up;k++)s[k]--;
		h++;
		}
	while(j<K&&i-d[j]%2000<M)
		{down=d[j]/2000;up=down+M-1<N?down+M-1:N;
		for(k=down;k<=up;k++)s[k]++;
		j++;
		}
	k=max();
	if(s[k]>best){best=s[k];y=k;x=i;}
	if(j>=K)break;
	}
	cout<<x-M<<' '<<y-M<<endl;
}
int cmp(long a,long b)
{return a%2000>b%2000;}

int main()
{int t,i;double a,b;
cin>>t;
while(t--)
{cin>>K>>N>>M;
for(i=0;i<K;i++){cin>>a>>b;d[i]=(long(a)+1)+2000*(long(b)+1);}

sort(&d[0],&d[K],cmp);
for(i=0;i<=N;i++)s[i]=0;
find();
}
return 0;
}