2291:Rotten Ropes

PKU

keyword

C++

概要

n(<1000)本のロープがあり、それぞれに強度t_iが与えられる。k本のロープで重さwの物体を持ち上げるとき、w/k>t_iならロープiは千切れる。持ち上げることができる最大の物体の重さを求める問題。
weakest linkよろしく一番弱いものが耐えきればよいので強度の高い順にソートしてk本使うときの最大値を順に調べていけばよい。

int main(){
    int rept, n, ans, ns[1002], i;
    scanf("%d",&rept);

    while(rept--){
        scanf("%d",&n);
        REP(i,n)scanf("%d",ns+i);
        sort(ns,ns+n,greater<int>());

        ans = 0;
        REP(i,n) ans = max(ans, ns[i]*(i+1));
        printf("%d\n",ans);
    }

    return 0;
}