【CodeForces-812C】Sagheer and Nubian Market【二分】

【CodeForces-812C】Sagheer and Nubian Market【二分】

Solution:

二分数量。按照下面的解决方案需要注意sum可能会爆掉,但是根据合法数据的s,是不会爆掉的,所以只要爆整数范围就认为当前试验的数量太多了,直接进入左区间。

每次需要排序,故复杂度O(nlognlogn).

代码:

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;
int w;
struct Node {
    int val, id;
    bool operator < (const Node & n) const {
        return val + id * w < n.val + n.id * w;
    }
};

const int LIM = 1e5 + 10;
Node dat[LIM];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    LL s;
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        cin >> dat[i].val;
        dat[i].id = i + 1;
    }
    int l = 0, r = n;
    int mid;
    LL sum;
    while (l + 1 < r) {
        mid = (l + r) >> 1;
        w = mid;
        sort(dat, dat + n);
        sum = 0;
        for (int i = 0; i < mid && sum >= 0; i++)
            sum += dat[i].val + dat[i].id * mid;
        // cout << mid << ": " << sum << endl;
        if (sum >= s || sum < 0) r = mid;
        else l = mid;
    }
    w = l;
    sort(dat, dat + n);
    LL ansa = 0;
    for (int i = 0; i < l; i++)
        ansa += dat[i].val + dat[i].id * l;
    w = r;
    sort(dat, dat + n);
    LL ansb = 0;
    for (int i = 0; i < r; i++)
        ansb += dat[i].val + dat[i].id * r;
    if (ansb > s) cout << l << ' ' << ansa;
    else cout << r << ' ' << ansb;
    cout << '\n';
    return 0;
}