题目链接

解题思路

小坑有点多,CF这种不考算法的思维题需要多写一些。

  • 首先,这个连接是可以反向连接的,所以不需要考虑a[i]和b[i]的大小关系(使用abs()) 开始写的时候特判二者的大小关系实则没有必要

  • 其次是当a[i]和b[i]相等时,这意味着从此时开始必须重新计数。
    与之相对应的是当a[i]和b[i]不相等时,此时的数值可以并入左边已有的环。此时max取最优。

  • 最后一个害我没过的坑是,此时既可以并入左边,也有可能从此时开始重新计数。
    因为并入左侧,意味着必须舍弃两个接触点之间的长度;而两点之间的长度是有可能比左侧更长的。

总而言之是一道不错的题目,虽然这个题害我痛苦了一个小时+掉分。但是依然是使人思维严密的一个题目。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;

int T;
int n,m;
struct node{
    int len;
    int a,b;
}a[1000100];

signed main(){
    //freopen("data.txt","r",stdin);
    //freopen("C.out","w",stdout);
    cin>>T;
    while(T--){
        cin>>n;
        int maxx=0;
        int ans=0;//maxx记录当前的值,ans记录最大值
        for(int i=1;i<=n;i++){
            cin>>a[i].len;
        }
        for(int i=1;i<=n;i++){
            cin>>a[i].a;
        }
        for(int i=1;i<=n;i++){
            cin>>a[i].b;
        }
        if(n>=2){
            maxx=abs(a[2].b-a[2].a);
            maxx+=2;
            maxx+=a[2].len-1;
            ans=maxx;
        }
        for(int i=3;i<=n;i++){
            if(a[i].a!=a[i].b){//二者不相等,并入左侧
                maxx-=abs(a[i].b-a[i].a);
                maxx+=2; 
                maxx+=a[i].len-1;
                ans=max(maxx,ans);
            }
            if(a[i].a==a[i].b){//二者相等,重新计数
                maxx=0;
                maxx+=2;
                maxx+=a[i].len-1;
                ans=max(maxx,ans);
            }
            if(abs(a[i].b-a[i].a)+2+a[i].len-1 > maxx){//若从此时开始较优,更新之。
                ans=max(ans,abs(a[i].b-a[i].a)+2+a[i].len-1);
                maxx=abs(a[i].b-a[i].a)+2+a[i].len-1;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
分类: 补题

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注