Gym – 101466 J. Jeronimo’s List 桶排序

My Solution

题意：一共n个数字(3<=n<=3e7,  0<=ai<3e7 )，给出前面的m个(3<=m<=min(100, n))，a[i] = (a[i-m] + a[i-m+1]) % MOD，q个询问(1<=q<=1e4)，询问a[1,n]里的从小到大第bi大。

桶排序

先按照要求用a[1,m]构造出a[1,n]，然后这里n == 3e7，所以如果采用快速的比较排序算法如归并排序快速排序的时间复杂度是O(nlogn)会超时，因此我们想到可以使用线性排序方法桶排序(或者说计数排序)，建一个数组cnt[3e7+8]，扫一遍a数组，对于每一个ai，cnt[a[i]]++，最后扫一遍cnt数组，就可以把ai排好序了。

for(i = 0; i < MOD; i++){
while(cnt[i]){
a[ptr] = i;
ptr++;
cnt[i]--;
}

}

时间复杂度 O(n)

空间复杂度 O(n)

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long LL;
const int MAXN = 3e7 + 8;
const int MOD = 3e7;
int cnt[MAXN], a[MAXN];

int main()
{
    #ifdef LOCAL
    freopen("j.txt", "r", stdin);
    //freopen("j.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    int n, m, q, i, x;
    //cin >> n >> m >> q;
    scanf("%d%d%d", &n, &m, &q);
    for(i = 1; i <= m; i++) scanf("%d", &a[i]); //cin >> a[i];
    for(i = m+1; i <= n; i++){
        a[i] = a[i-m] + a[i-m+1] - (a[i-m] + a[i-m+1]) / MOD * MOD;
    }
    for(i = 1; i <= n; i++){
        cnt[a[i]]++;
    }
    int ptr = 0;
    for(i = 0; i < MOD; i++){
        while(cnt[i]){
            a[ptr] = i;
            ptr++;
            cnt[i]--;
        }
    }
    for(i = 0; i < q; i++){
        //cin >> x;
        scanf("%d", &x);
        //cout << a[x-1] << "\n";
        printf("%d\n", a[x-1]);
    }



    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

Source（）

Gym - 101466J

2017 ACM-ICPC, Universidad Nacional de Colombia Programming Contest

Thank you!

                                                                                                                                             ------from ProLightsfx