3665:iCow

keyword

シミュレーション　C++

概要

曲がN(<1000)曲あり、それぞれにレーティングが割り振られている。レーティングの高い曲から順に再生され、再生された曲のレーティングは別の曲に再分配される。初めからT(<1000)曲の再生順序を求める問題。
O(n^2)までいけるので特別なデータ構造を持たなくても愚直にシミュレーションすればよい。再分配のルールを勘違いしていて2WA位もらった。

typedef pair<int, int> pi;

int main(){
    int i, n, t, r, res, div;
    vector<pi> list;
    bool played[1001];
    REP(i,1001) played[i] = false;
    scanf("%d%d",&n,&t);

    REPONE(i,n){
        scanf("%d",&r);
        list.PB(MP(-r,i));
    }

    LOOP(t){
        sort(ALL(list));
        printf("%d\n",list[0].second);
        played[list[0].second] = true;
        r = -list[0].first;
        list[0].first = 0;
        div = r / (n-1);
        res = r % (n-1);
        REPONE(i,n) list[i].first -= div;
        int cnt = 0;
        if(list[0].second <= res){
            res++;
            cnt++;
        }
        for(i=1;i<n && res>cnt; i++){
            if(res >= list[i].second){
                list[i].first -= 1;
                cnt++;
            }
        }
    }

    return 0;
}