ABC246C Coupon Solution

• ABC246C Coupon Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

$ n $ 个物品第 $ i $ 个价格为 $ a_i $，有 $ k $ 张 $ x $ 元优惠券，可以叠加，但不能分裂开使用，求全部购买的最少花费。

Solution

在还有优惠券的前提下，对于所有 $ a_i \ge x $ 一直使用优惠券直到 $ a_i \lt x $，然后降序排序用剩余的 $ k $ 个券贪心地把前 $ k $ 个抵消，后面的求和即为答案。

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;
using namespace __gnu_pbds;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template<typename T = int>
inline T read(void);

int a[210000];

int main(){
    int N = read(), K = read(), X = read();
    for(int i = 1; i <= N; ++i){a[i] = read();while(K && a[i] >= X)--K, a[i] -= X;}
    sort(a + 1, a + N + 1, greater < int >());
    ll ans(0);
    for(int i = K + 1; i <= N; ++i)ans += a[i];
    printf("%lld\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template<typename T>
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2022_10_21 初稿