[ABC270E] Apple Baskets on Circle Solution

更好的阅读体验戳此进入

题面

存在 $n$$n$ 个筐围成一圈，第 $i$$i$ 个有 $A_i$$A_i$ 个苹果。你需要从第 $1$$1$ 个筐开始依次拿掉一个苹果，直到拿了 $k$$k$ 个。如果筐内没有苹果那么直接拿下一个筐。求最终每个筐里还剩多少个苹果。

Solution

题解区怎么都是二分答案的做法，来一发 VP 时糊出来的更加无脑的模拟做法。

首先假设一圈里有 $k$$k$ 个篮子里有苹果，那么转一圈一定会拿走 $k$$k$ 个苹果，然后当拿空了一个篮子之后就会 $k\leftarrow k-1$$k \leftarrow k - 1$。所以我们考虑维护一下当前一共还有多少个篮子里有苹果，然后给所有 $A_i$$A_i$ 排个序，每次取最小的然后判断是否能拿空，如果可以的话那么直接拿空，否则尽量拿多圈，此时剩下的所有显然不足一圈，此时再次遍历一遍即可。

然后注意其中有一步 $cur\times v$$cur \times v$，这个东西我感觉似乎是 ${10}^{24}$$10^{24}$ 级别的，于是开了个 __int128_t。

审核没通过，说太简略了，那么就把具体过程再说一下吧：

维护一个 $minus$$minus$ 表示当前一共拿过了多少圈，每次取一个苹果数最小的篮子并去掉已经拿走的 $minus$$minus$ 个，然后考虑现在剩下的有苹果的篮子数，即 $cur$$cur$ 乘上最小的剩的苹果数，如果可以全部取走那么就都取走，然后 $minus\leftarrow minus+v$$minus \leftarrow minus + v$。反之尽量拿更多圈，记录剩余多少个苹果没拿，显然其会小于剩余的存在苹果的篮子数，此时暴力枚举跑一下即可。

Code

xxxxxxxxxx
60
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.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 void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10

11
using namespace std;
12

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

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

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

25
int N; ll K;
26
ll A[210000];
27
priority_queue < ll, vector < ll >, greater < ll > > buc;
28

29
int main(){
30
    N = read(), K = read < ll >();
31
    ll cur(0);
32
    for(int i = 1; i <= N; ++i)if((A[i] = read < ll >()))buc.push(A[i]), ++cur;
33
    ll minus(0);
34
    while(!buc.empty()){
35
        ll v = buc.top() - minus; buc.pop();
36
        if((__int128_t)cur * v <= K)K -= cur * v, minus += v, --cur;
37
        else{minus += K / cur, K -= K / cur * cur; break;}
38
    }
39
    for(int i = 1; i <= N; ++i)A[i] = max(0ll, A[i] - minus);
40
    for(int i = 1; i <= N && K; ++i)if(A[i])--A[i], --K;
41
    for(int i = 1; i <= N; ++i)printf("%lld%c", A[i], i == N ? '\n' : ' ');
42
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
43
    return 0;
44
}
45

46
template < typename T >
47
inline T read(void){
48
    T ret(0);
49
    int flag(1);
50
    char c = getchar();
51
    while(c != '-' && !isdigit(c))c = getchar();
52
    if(c == '-')flag = -1, c = getchar();
53
    while(isdigit(c)){
54
        ret *= 10;
55
        ret += int(c - '0');
56
        c = getchar();
57
    }
58
    ret *= flag;
59
    return ret;
60
}

UPD

update-2023_01_27 初稿

update-2023_02_01 审核没过，将叙述改的更详尽一些