题目描述

难度分:$1500$

输入$n(1 \leq n \leq 10^5)$，$s(1 \leq s \leq 10^9)$和长为$n$的数组$a(1 \leq a[i] \leq 10^5)$。

有$n$个物品，每个物品至多买一个。假设你买了其中的$k$个，那么对于这$k$个物品，每个物品$a[i]$的花费为$a[i]+i \times k$元。下标从$1$开始。

你有$s$元钱，最多可以买多少个物品？钱不需要恰好花完。

假设你最多买了$k$个，输出$k$以及购买$k$个物品的最小花费。

输入样例$1$

3 11
2 3 5

输出样例$1$

2 11

输入样例$2$

4 100
1 2 5 6

输出样例$2$

4 54

输入样例$3$

1 7
7

输出样例$3$

0 0

算法

二分答案+贪心

比较容易想到要二分这个$k$，因为买得越多，花费肯定是越高的。而对于给定的$k$，我们将$a$数组按照$a[i]+i \times k$排序（也可以通过快选得到$topk$，这样时间复杂度为$O(n)$，是更低的），前面$k$个最小的花费加起来就是购买$k$件物品的最小花费。

如果花费$\leq s$就记录答案并往右搜索看能不能更大，否则就往左搜索。这样在二分出$k$的同时，也得到了购买$k$件物品的最小花费。

复杂度分析

时间复杂度

在$[0,n]$区间上进行二分答案，时间复杂度为$O(log_2n)$，每次$check$需要排序，时间复杂度为$O(nlog_2n)$，之后$O(k)$计算最小花费。因此，整个算法的时间复杂度为$O(n(log_2n)^2)$。

空间复杂度

需要开辟空间存每个$a[i]$对应的编号，空间复杂度为$O(n)$。每次$check$都需要排序，以快排为基准，空间复杂度为$o(log_2n)$。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int n, s, a[N];
struct item {
    int a, i;
} items[N];

LL check(LL k) {
    LL cost = 0;
    sort(items + 1, items + n + 1, [&](auto& i1, auto& i2) {
        return i1.i*k + i1.a < i2.i*k + i2.a;
    });
    for(int i = 1; i <= k; i++) {
        cost += items[i].i*k + items[i].a;
    }
    return cost;
}

int main() {
    scanf("%d%d", &n, &s);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &items[i].a);
        items[i].i = i;
    }
    int l = 0, r = n;
    LL ans = 0;
    while(l < r) {
        int mid = l + r + 1 >> 1;
        LL cost = check(mid);
        if(cost <= s) {
            ans = cost;
            l = mid;
        }else {
            r = mid - 1;
        }
    }
    printf("%d %lld\n", r, ans);
    return 0;
}