#不変量 #貪欲法
残す値の個数の最大値がもとまれば、消す値の個数の最小値がわかるので、前者を考えることにする。
この問題において、数列
\(A\)
の値の総和と所持しているお金の合計は一定である。つまり、目標の数列
\(B\)
があって、
\(\sum A \geq \sum B\)
であるならば数列Bを構成可能であると言える。また、「長さ
\(x\)
のいい数列
\(B\)
であって、総和を最小とするような数列は何か?」を考えると、これは素数を小さい方から
\(x\)
個並べた列である
。
よって、以下の問題を高速に解くことができれば元の問題が解ける。なお、
\(A\)
は降順にソートされている
とし
\(B\)
は素数を小さい方から並べた数列であるとする。
以下を満たす \(x\) の最大値を求めよ。
\(\sum_{i=1}^x A_i \geq \sum_{i=1}^x B_i\)
\(A\)
も
\(B\)
もすでに決まっているので前から順に判定しても良いし、条件には単調性があるので二分探索を用いることもできる。
提出
vll primes=Eratosthenes(1e7);
void solve() {
int n; cin >> n;
auto a=i64_vec_IN(n);
sort(all(a));
reverse(all(a));
ll ok = 1;
ll ng = n+1;
while(abs(ok-ng)>1) {
ll mid = (ok+ng)>>1;
ll sa=0;
ll sp=0;
rep(i,mid){
sa+=a[i];
sp+=primes[i];
}
if(sa>=sp)ok=mid;
else ng=mid;
}
cout << n-ok << '\n';
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int t=1;
cin >> t;
while(t--)solve();
}
エラトステネスの篩を前計算し、
\(M\)
を「
\(N\)
番目の素数」とする。
ソートがボトルネックとなり、
\(O(N\log N + M\log \log M)\)
時間となる。