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

小红的小踏前斩

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);


}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-10 11:45
你不要过来啊啊啊啊啊啊啊
码农索隆:对面:“今天你不面也得面”
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-10 13:54
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务