Znzryb's Blog
0%

牛客小白月赛-104-C-小红打怪

Posted on Edited on

AC代码

我是没想到赛时能过

主要就是check函数难写

全体攻击和单体攻击都没什么好说的，都不可能浪费

只有群体攻击有可能浪费，那么就先算一下群体攻击能不浪费的打多少次

接着打单体，单体打完了浪费的打群体

比较复杂，我以为过不了，但竟然过了，AC！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(1e5)+10;
ll n,A[N],rangeR;

inline bool check(ll mid) {
    vector<ll> remain(n + 5);
    // 计算每个怪物在全体攻击后剩余的血量
    for (int i = 1; i <= n; ++i) {
        remain[i] = A[i];
    }
    ll sumD=0,sumF=0;
    bool isBreak=false;
    for(int i=1;i<=n;++i) {     // 这次是范围打击，我们尽量让范围打击不浪费，因为其他两种打击是不可能浪费的
        if(remain[i]-mid<=0)
            continue;
        ll fanAtt=min(remain[i]-mid,remain[i+1]-mid);
        sumF+=fanAtt;
        if(sumF>=mid) {
            // mid-sumFup 就是这次最多能减的值
            fanAtt=mid-(sumF-fanAtt);
            sumF=mid;
            isBreak=true;
        }
        remain[i]-=fanAtt;remain[i+1]-=fanAtt;
        if(isBreak)
            break;
    }
    // 不浪费的范围打击已经在上面释放完了
    bool isD=true;
    for(int i=1;i<=n;++i) {
        if(remain[i]-mid<=0)
            continue;
        if(isD) {
            sumD+=remain[i]-mid;
            if(sumD>=mid) {
                // 多加的=另外一个需要的
                sumF+=(sumD-mid);
                remain[i+1]-=(sumD-mid);
                isD=false;
            }
        }else {
            sumF+=remain[i]-mid;
            remain[i+1]-=remain[i]-mid;
        }
    }
    if(sumF<=mid)
        return true;
    return false;
}

inline ll bsearch() {
    ll l=0,r=rangeR;
    while (l<r) {
        ll mid=l+r>>1;
        if(check(mid))  // 能杀，说明可能太多了回合数
            r=mid;
        else
            l=mid+1;
    }
    return l;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i) {
        cin>>A[i];
        rangeR=max(rangeR,A[i]);
    }
    cout<<bsearch()<<endl;
}
// AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=73037080

心路历程（WA，TLE，MLE……）

这个WA掉的程序主要是修改了A的值，应该还是最好不要这么干

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(1e5)+10;
ll n,A[N],rangeR;

inline bool check(ll mid) {
    // bool isEff=false,upRemain=0;
    ll sumD=0,sumF=0;
    bool isBreak=false;
    for(int i=1;i<=n;++i) {     // 这次是范围打击，我们尽量让范围打击不浪费，因为其他两种打击是不可能浪费的
        if(A[i]-mid<=0)
            continue;
        ll fanAtt=min(A[i]-mid,A[i+1]-mid);
        sumF+=fanAtt;
        if(sumF>=mid) {
            fanAtt=mid-(sumF-fanAtt);
            sumF=mid;
            isBreak=true;
        }
        A[i]-=fanAtt;A[i+1]-=fanAtt;
        if(isBreak)
            break;
    }
    // 不浪费的范围打击已经在上面释放完了
    bool isD=true;
    for(int i=1;i<=n;++i) {
        if(A[i]-mid<=0)
            continue;
        if(isD) {
            sumD+=A[i]-mid;
            if(sumD>=mid) {
                // 多加的=另外一个需要的
                sumF+=(sumD-mid);
                A[i+1]-=(sumD-mid);
                isD=false;
            }
        }else {
            sumF+=A[i]-mid;
            A[i+1]-=A[i]-mid;
        }
    }
    if(sumF<=mid)
        return true;
    return false;
}

inline ll bsearch() {
    ll l=0,r=rangeR;
    while (l<r) {
        ll mid=l+r>>1;
        if(check(mid))  // 能杀，说明可能太多了回合数
            r=mid;
        else
            l=mid+1;
    }
    return l;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i) {
        cin>>A[i];
        rangeR=max(rangeR,A[i]);
    }
    cout<<bsearch()<<endl;
}