题目的意思是,一共有N个人,给出一个函数,再通过给出a、b、c变量可以计算出第N个人的分数,然后接下来有M场比赛,每场比赛由产生的n个数中从小到大排序,排到第n-1大的人来进行,问这第个人的分数是多少?


排序好题,由于n高达10e7,所以直接排序铁定超时,可以利用快排思想来解决,先选定一个基准数,然后排序,排完后这个数的位置就确定了,然后根据查询的数是否大于还是小于这个数可以选择一边排序而没有必要全排了,所以时间就降下来了。但是本人太low啊,写了两遍都TLE,所以看STL中有个nth_element函数,就用他水过了。。。


地址:http://acm.hdu.edu.cn/showproblem.php?pid=6040


代码:

StatusAccepted
Time1918ms
Memory79960kB
Length1173
LangC++


#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10000005;
const int maxm=105;
long long data[maxn],ans[maxm];
int q[maxm], pos[maxm];
unsigned n, m, a, b, c, x, y, z, cas=0;
unsigned rng61() {
  unsigned t;
  x ^= x << 16;
  x ^= x >> 5;
  x ^= x << 1;
  t = x;
  x = y;
  y = z;
  z = t ^ x ^ y;
  return z;
}
bool cmp(int ca, int cb){return q[ca]<q[cb];}
int main()
{
    while(~scanf("%u%u%u%u%u", &n, &m, &a, &b, &c)){
        for(int i=0;i<m;i++){
            scanf("%u", &q[i]);
            pos[i]=i;
        }
        x=a;y=b;z=c;
        for(int i=0;i<n;i++){
            data[i]=rng61();
        }
        sort(pos, pos+m, cmp);
        pos[m]=m;
        q[m]=n;
        for(int i=m-1;i>=0;i--){
            if(q[pos[i]]==q[pos[i+1]]){
                ans[i]=ans[i+1];
            }
            else{
                nth_element(data, data+q[pos[i]], data+q[pos[i+1]]);
                ans[i]=data[q[pos[i]]];
            }
        }
        printf("Case #%u:", ++cas);
        for(int i=0;i<m;i++){
            printf(" %lld", data[q[i]]);
        }
        printf("\n");
    }
    return 0;
}