cf 684D - Traps

贪心推公式题

对于  如果我们跳过它跳过的花费为

可见只要0" src="https://latex.codecogs.com/gif.latex?f%28i%29%3E0" />跳过便一定能够取得更小的花费，根据目数据限制 可知该条件一定成立，故而需要跳过全部m次

对于所有的跳过，跳过的花费为

通过观察我们可以发现后面一项求和为常数即(最好不要改动，因为c++的除法是整除)对于b[i]=a[i]-(n-i)由大到小排序

根据定义

#include
#include
#include

using namespace std;

typedef long long ll;
const int N = 200005;
int a[N],b[N];
int n, m;
ll ans;

int main()
{
    int _; cin >> _;
    while (_--)
    {
        ans = 0;
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            ans += a[i];
        }
        for (int i = 1; i <= n; i++)
            b[i] = a[i] - (n - i);
        sort(b + 1, b + 1 + n, greater());
        for (int i = 1; i <= m; i++)
            ans -= b[i];
        ans = ans - (ll)m*(m-1)/2;
           cout << ans << endl;
    }
    return 0;
}