CF1654A

崔化博 · 2022-03-22 09:31:13 · 题解

题目大意

给出一个序列，可以将一个字段翻转，求最大相邻两个数的和。

思路

根据题目模拟翻转字段的左端点和右端点即可，我们注意到翻转后只会变两个数，也就是左右端点。于是，代码出来了。

#include <iostream>
#include <cstdio>
#include <algorithm> 
using namespace std;
int t,n,a[1005],maxn;
int main(){
    scanf("%d",&t);
    while(t--){
        maxn=0;
        scanf("%d",&n);
        for(register int i=1;i<=n;++i){
            scanf("%d",&a[i]);
            maxn=max(maxn,a[i]+a[i-1]);
        }
        for(register int i=1;i<n;++i){
            for(register int j=i+1;j<=n;++j){
                maxn=max(maxn,max(a[i-1]+a[j],a[i]+a[j]));
            }
        }       
        printf("%d\n",maxn);
    }
    return 0;
}

这就A了，但是我们可以继续优化。

考虑任何一组数列，都可以把最大数和第2大数挨在一起。因为我们可以翻转最大数右边的数到第2大数这个数列，使得最大数和第2大数挨在一起。

#include <iostream>
#include <cstdio> 
using namespace std;
int t,n,a[1005],maxn1,maxn2;
int main()
{
    scanf("%d",&t);
    while(t--){
        maxn1=maxn2=0;
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
            if(a[i]>maxn1)maxn2=maxn1,maxn1=a[i];//如果有比最大还大的数，就先把最大的赋给第2大的，然后最大的再赋值
            else if(a[i]>maxn2)maxn2=a[i];
        }
        printf("%d\n",maxn1+maxn2);
    }
    return 0;
}