codeforces 1671C

发布时间:2023年12月28日

一道推公式的题,推公式小白的我直接交了一发 t 3 t3 t3 c o d e code code
题目链接

题目大意

n n n家商店,第 i i i家售卖白糖价格是 a [ i ] a[i] a[i],每天每家商店都会在原有价格基础上加 1 1 1,每天的预算为 x x x,问可以买到的最大数量包为多少

思路

预算为 x x x时,第 j j j天能从第 i i i家商店购买白糖的条件是:
x > = ∑ k = 1 n a [ i ] + ( j ? 1 ) ? i x>=\sum_{k=1}^{n}a[i]+(j-1)*i x>=k=1n?a[i]+(j?1)?i
所以咱们倒过来累加一下就行了
注意要开 l o n g l o n g longlong longlong

ACcode

#include<bits/stdc++.h>

using ll = long long;

using namespace std;

void solve()
{
    int n, x;cin >> n >> x;
    vector<int>a(n + 3);
    for (int i = 1;i <= n;i++)cin >> a[i];
    sort(a.begin() + 1, a.begin() + 1 + n);
    for (int i = 1;i <= n;i++)a[i] += a[i - 1];
    ll ans = 0;
    for (int i = 1;i <= n;i++) {
        if (a[i] > x)break;
        ans += (x - a[i]) / i + 1;
    }
    cout << ans << '\n';
}

int main() {
    int t;cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
文章来源:https://blog.csdn.net/weixin_70831807/article/details/135276398
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。