uva 10474 Where is the Marble? 計數排序

題目給出一系列數字，然後問哪個數字是從小到大排在第幾的，重復出現算第一個。

數據范圍為10000，不大，完全可以暴力，sort不會超時。

但是由於以前做比賽時也遇到這種題目，沒注意看數據范圍，然後暴力被hack了。之後就學會了計數排序了。

這題也用計數排序做，挺快的，代碼也不長。

代碼：

#include <cstdio>   
#include <cstring>   
const int maxn = 10001;  
  
int num[maxn], s[maxn];  
  
int main() {  
    int n, q, tmp, m = 0, cnt = 0;  
    while (scanf("%d%d", &n, &q) && (n || q)) {  
        printf("CASE# %d:\n", ++cnt);  
        memset(num, 0, sizeof(num));        //init   
        memset(s, 0, sizeof(s));  
        for (int i = 1; i <= n; i++) {       //input   
            scanf("%d", &tmp);  
            if (m < tmp)  
                m = tmp;  
            num[tmp]++;  
        }  
        int sum = 0;  
        for (int i = 1; i <= m; i++)     //calc the sum   
            s[i] = s[i - 1] + num[i];  
        for (int i = 1; i <= q; i++) {       //output   
            scanf("%d", &tmp);  
            if (num[tmp])  
                printf("%d found at %d\n", tmp, s[tmp - 1] + 1);  
            else  
                printf("%d not found\n", tmp);  
        }  
    }  
    return 0;  
}