ABC246C Coupon Solution

更好的阅读体验戳此进入

题面

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

Solution

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

Code

xxxxxxxxxx
53
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

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

11
using namespace std;
12
using namespace __gnu_pbds;
13

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

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

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

26
int a[210000];
27

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

39
template<typename T>
40
inline T read(void){
41
    T ret(0);
42
    short flag(1);
43
    char c = getchar();
44
    while(c != '-' && !isdigit(c))c = getchar();
45
    if(c == '-')flag = -1, c = getchar();
46
    while(isdigit(c)){
47
        ret *= 10;
48
        ret += int(c - '0');
49
        c = getchar();
50
    }
51
    ret *= flag;
52
    return ret;
53
}

UPD

update-2022_10_21 初稿