美味い飯食わせろ2020+1円分
よし,問題が解けない.
問題が解けないことが問題なのだ.
ところで,Typoraを使ってブログ書いてるんだけど,Space Space Shift+エンター で改行が出来るらしい.試すぞ.
ぉぉ,すげえ,これブラウザ上でも改行されるのかな.分からん
これの何が良いって,日本語入力モードでも すぺーす すぺーす しふぷらえんた で改行できるのがいいね.
よし.んじゃ行くぞ.
追記,下,解くの一旦諦めました.読まないほうがいいです.
ABC205 D- Kth Excluded
[数列に含まれないK番目に小さい数,クエリ処理]
これを…解くのです… ちなみに,今回の内容は,解いた後に書くんじゃなくて,書きながら解きます.
なんか,このブログ書き始める前は,数列に存在しない数を区間として配列に格納していこう.みたいなことをしていました.
int main() { int n, q; cin >> n >> q; vector<ll> a(n); rep(i,n) cin >> a[i]; SORT(a); ll from = 1; vector<P> section; rep(i,n){ ll to = a[i] - 1; from = a[i] + 1; if(from > to) continue; else { section.push_back(P(from,to)); printf("[%lld, %lld]\n", from, to); } } }
数列 A = {3, 5, 6, 7}なとき, 区間は,[1,2], [4,4], [8,inf]みたいな感じで取れるんだけど,そっからどうしたらいいか分からん.違うやり方思いついた.
あたらしいやりかた
クエリがQ個与えられて,K1,K2,...,Kqがあるわけだけど,これを(K1 < k2 < ,..., < Kq)となるように並び替えれば,計算量が抑えられる気がするタピ!!(タピちゃん)
とりあえず,クエリを並び替えても答えを出力するときに順序が保てるようにしないとね!!
とりあえずやってみよう!!
あ,そうそう,数列Aはソートしても全く問題ないよね.全く問題ないので.
typdef pair<ll,ll> P;
vector<P> query(q);
rep(i,q){
int x;
cin >> x;
query[i] = P(x,i);
}
SORT(query);
良し,これでKiを若い順に並び替えても,もともとのクエリの順序がqueryのセカンド要素に保持されることになる.よっしゃ.いいぞ,もっとやれ.
さて,こっからどうするか.マジで競プロさぼりすぎてたせいで考えるのがめんどくさいんだよな.この問題も取り組み始めてから2時間ぐらいかかってる気がする.
キタキタキタキタキタ,北埼玉