题解 | #小红的小踏前斩#

小红的小踏前斩

https://www.nowcoder.com/practice/aa428da6310a4e889bad5bae59f89025

#include <cstdio>
#include <iostream>
#include <vector>
#include "bits/stdc++.h"
using namespace std;
const int maxn = 2e5+20;
int A[maxn];
using pr = pair<int, int>;
using ll  = long long;
int main() {
    int n;
    scanf("%d",&n);
    vector<pr>vec(n);
    for(int i =0;i<n;i++)  
    {
        int x;
        scanf("%d",&x);
        vec[i] = {x,i};
        A[i] = x;
    }
    /*
        1,两个怪相隔着,分开杀(砍他的前一个)
        2. 两个怪连着,一起杀
        (1)直接砍前一个,后面的也4
        (2)先砍这个把后一个砍4,然后再砍前一个,把他砍4
    */
    std::sort(vec.begin(),vec.end());
    //分开杀
    pr p1 = vec[0],p2 = vec[1];
    // printf("%d %d\n",p1.first,p2.first);
    ll ans = 2e18+10;
    ll sum = 0;
    if(p1.second!=0){
        sum+=(p1.first+1)/2;
    }
    else {
        if(n>2){
            pr p3 = vec[2];
            sum+=min((p3.first+1)/2,p1.first);
        }
        else{
            sum+=p1.first;
            // printf("%lld\n",sum);
        }
    }
    if(p2.second!=0){
        sum+=(p2.first+1)/2;
                    // printf("%lld\n",sum);
    }
    else {
        if(n>2){
            pr p3 = vec[2];
            sum+=min((p3.first+1)/2,p2.first);
        }
        else{
            sum+=p2.first;
        }
    }
    ans = min(ans,sum);
    // printf("%lld\n",ans);
    //连着鲨
    for(int i = 1;i<n-1;i++){
        //砍他妈的,然后把后面的也砍死
        // int tmp=0;
        ll tmp1 = max(A[i],(A[i+1]+1)/2);
        //先把他后面那个砍死,再用上一个把i砍死   
        ll tmp2 = (A[i+1]+1)/2;
        int ai =A[i]-tmp2;
        tmp2+=max((ai+1)/2,0);
        ans = min(ans,min(tmp1,tmp2));
    }
    //第一个只有直接砍死
    ans = min(ans,1LL*max(A[0],(A[1]+1)/2));
    printf("%lld\n",ans);


}

全部评论

相关推荐

04-02 22:40
已编辑
电子科技大学 后端
谢谢大家啦!!!
坚定的芭乐反对画饼_许愿Offer版:有鹅选鹅,没鹅延毕
点赞 评论 收藏
分享
ALEX_BLX:虽然说聊天记录不可信,不过这个趋势确实如此但我觉得也要想到一点就是卷后端的人里真正有“料”的人又有多少,我说的这个料都不是说一定要到大佬那种级别,而是就一个正常的水平。即使是现在也有很多人是跟风转码的,2-3个月速成后端技术栈的人数不胜数,但今时不同往日没可能靠速成进大厂了。这种情况就跟考研一样,你能上考场就已经打败一半的人了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务