[Codeforces] Round #538 B. Yet Another Array Partitioning Task

Yet Another Array Partitioning Task

https://codeforces.com/contest/1114/problem/B

考え方

題意

配列 \( a \) の連続する要素からなる部分配列のサイズが \( m \) 以上かつそのような部分配列を \( k \) 個作ります。このとき、ある要素は一つの部分配列に入っているとします。各部分配列の要素の大きい値から \( m \) 個の和がその部分配列の評価値とします。全ての部分配列の評価値の和が最大となるとき、その最大値と部分配列の区切りの値を \( k – 1 \) 個出力します。

方針

良く分からなかったので、解説を読みました。

まず最大値は、配列を降順に並び替え、先頭から \( mk \) 個の和が最大値となります。区切りの値は、\( mk \) 個の添え字を昇順に並び替え、\( m \) 個ずつ取り出したものが、区切りの値となります。

コード

感想

あまり理解できませんでした。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする