贪心只有#7错了,,有人遇到吗
查看原帖
贪心只有#7错了,,有人遇到吗
694213
AlohaHenry楼主2023/11/10 12:13
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5+5, H = 1e6+5;
int n, ans, a[N], flag;

int find(int flag){
    int x = flag ? -1 : H;
    int ret = 0;
    for(int i=0;i<n-1;i++){
        if(a[i]>=x&&flag==1)//我是成对判断
            ret += 2, flag=0, x = a[i];// printf("case1: i %d\n", i);
        else if(a[i]>=x&&flag==0) x = a[i];// 如果下一个数更大但当前无法上升,不加ret
        else if(x>a[i]) x = a[i], flag=1;// 如果下降选最小
    }
    int i = n-1;//最后特判
    if(a[i]>=x&&flag==1) ret += 2;
    else if(x>a[i]) ret+=1;
    return ret;
}

int main(){
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> a[i];
    ans = find(0);//下降
    ans = max(ans, find(1)-1);//一开始上升
    cout << ans;
}

结果差了36,不是边界

2023/11/10 12:13
加载中...