JOI 2025/2026 二次予選 : D - 買い物 3 (Shopping 3)

最初問題文誤読してしまった。
https://atcoder.jp/contests/joi2026yo2/tasks/joi2026_yo2_d

問題

N個の商品があり、i個目の価格はA[i]である。
以下のクエリに答えよ。

• パラメータC,Dが与えられる。
• チケットを１枚使うと、各商品の価格がD安くなる。ただし各商品の価格は0未満にはならない。また、１枚ごとに追加料金がCかかる。
• 最適な枚数チケットを使うとき、全商品を買うための総価格の最小値を求めよ。

解法

価格を事前にソートしておき、累積和を取れば、チケット枚数に対する総価格をO(logN)で求められる。
あとはチケット枚数を三分探索しよう。

int N;
int Q;
ll A[303030];
ll S[303030];
ll C,D;

ll hoge(ll k) {
	ll dk=D*k;
	int x=lower_bound(A,A+N,dk)-A;
	ll sum=(S[N]-S[x])-(1LL*(N-x)*(dk))+C*k;
	return sum;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>A[i];
	}
	sort(A,A+N);
	FOR(i,N) S[i+1]=S[i]+A[i];
	while(Q--) {
		cin>>C>>D;
		ll L=0,R=(1<<30)/D+1;
		ll ret=hoge(0);
		while(R-L>=10) {
			ll M1=(L*2+R)/3;
			ll M2=(L+R*2)/3;
			ll V1=hoge(M1);
			ll V2=hoge(M2);
			if(V1<=V2) R=M2;
			if(V2<=V1) L=M1;
			ret=min(ret,V1);
			ret=min(ret,V2);
		}
		for(i=L;i<=R;i++) ret=min(ret,hoge(i));
		cout<<ret<<endl;
	}
}

まとめ

チケット１枚で１商品だけ値下がりすると勘違い。
その場合すんなり解けるかな？