题解：CF812C Sagheer and Nubian Market

GLr137 · 2025-05-03 12:01:08 · 题解

我们可以通过二分纪念品的数量来解决这道题，由于是求最小值，所以我们用左答案来解决，而 check 函数里直接用贪心来得出每件纪念品的花费，排序后算出前 k 项的和与 S 进行比较即可。

注意要用到排序，且过程中最好把所有都设成 long long，否则结果会惨不忍睹。

代码

# include <bits/stdc++.h>
using namespace std;
long long sum2, n, s, l, r, mid, ans, a[100005], sz[100005];
bool check (int k){
    long long sum = 0;
    for (long long i = 1; i <= n; i++){
        sz[i] = a[i] + i * k;
    }
    sort(sz + 1, sz + n + 1);
    for (long long i = 1; i <= k; i++){
        sum += sz[i];
    }
    return sum <= s;
}
int main (){
    cin >> n >> s;
    for (long long i = 1; i <= n; i++){
        cin >> a[i];
    }
    l = 1;
    r = n;
    while (l <= r){
        mid = l + (r - l) / 2;
        if (check(mid)){
            ans = mid;
            l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    cout << ans << " ";
    for (long long i = 1; i <= n; i++){
        sz[i] = a[i] + i * ans;
    }
    sort(sz + 1, sz + n + 1);
    for (long long i = 1; i <= ans; i++){
        sum2 += sz[i];
    }
    cout << sum2;
    return 0;
}