#417 Div2 C

题意

给出 n 个货物的基础价格和钱 S ，每个货物的最终价格要加上 购买商品总数 * 商品在原来序列中的序号。

问最多能买多少件，且花费最小。

分析

二分购买商品数量，每次判断前给商品排序。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

int n;

ll S;

struct A {

    int i, num;

}a[MAXN];

ll K;

int cmp(A o1, A o2) {

    return (ll)o1.i * K + o1.num < (ll)o2.i * K + o2.num;

}

ll get(int k) {

    ll res = 0;

    for(int i = 0; i < k; i++) {

        res += a[i].num + a[i].i * k;

    }

    return res;

}

int main() {

    ios::sync_with_stdio(0);

    cin.tie(0);

    cin >> n >> S;

    for(int i = 0; i < n; i++) {

        cin >> a[i].num;

        a[i].i = i + 1;

    }

    int l = 0, r = n, mid = l, ans = 0;

    while(l <= r) {

        mid = (l + r) / 2;

        K = mid;

        sort(a, a + n, cmp);

        if(get(mid) <= S) {

            ans = mid;

            l = mid + 1;

        } else {

            r = mid - 1;

        }

    }

    cout << ans << " " << get(ans) << endl;

    return 0;

}