1968.txt

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

#include<stdio.h>
#include<stdlib.h>
#define debug 0
#define NMAX 3005
struct data
{
    long page;
    int index;
}m[NMAX];
int cmp(void const *a,void const *b)
{
    if((*(struct data*)a).page==(*(struct data*)b).page)
        return (*(struct data*)b).index-(*(struct data*)a).index;
    else
        return (*(struct data*)a).page-(*(struct data*)b).page;

}
main()
{
#if debug
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
    long n,q,k,t;
    long a,b,i,j;
    long min,r;
    
    
    while(scanf("%ld%ld%ld",&n,&q,&k)!=EOF)
    {
        b=k%n;
        a=k/n;
        for(i=0;i<k;i++)
        {
            scanf("%ld",&m[i].page);
            m[i].index=i;
        }
        qsort(m,k,sizeof(struct data),cmp);
        t=q+1;
        if(t<=b)
        {
            r=m[(t-1)*(a+1)+1-1].page;
            min=m[(t-1)*(a+1)+1-1].index;
            for(i=(t-1)*(a+1)+2-1;i<=t*(a+1)-1;i++)
            {
                if(min>m[i].index)
                {
                    min=m[i].index;
                    r=m[i].page;
                }
            }
        }
        else
        {
            r=m[b*(a+1)+((t-b)-1)*a+1-1].page;
            min=m[b*(a+1)+((t-b)-1)*a+1-1].index;
            for(i=b*(a+1)+((t-b)-1)*a+1-1+1;i<=b*(a+1)+(t-b)*a-1;i++)
            {
                if(min>m[i].index)
                {
                    min=m[i].index;
                    r=m[i].page;
                }
            }
        }
        printf("%ld\n",r);
        
    }



#if debug
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}