No.1897 Sum of 2nd Max
自力AC。コンテスト中も正しい方針を考えていたのだけど、詰め切れなかった。
NとKの制約が両方$2*10^5$以下なので、どちらかしか全探索できないが、要素の総和を求める、ということなので、「あるxが大きい方から2番目になるような数列の個数」を考えた方が良さそう。
その際、
・xより大きいものが一個、それ以外はx以下
・全てx以下
の二通りに分け、前者からは「xが含まれない場合」を除く。後者からは「xが一個も含まれない場合」および「xが一個だけ含まれる場合」を除くと考えると計算できる。
0 件のコメント:
コメントを投稿