#417 Div2 C

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

#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;
}