交叉线

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

bool F(int l1, int r1, int l2, int r2){
    return (l2<r1 && l2>l1 && r2>r1) || (r2<r1 && r2>l1 && l2<l1);
}

int main(){
    int T,n,l1,r1,l2,r2;
    cin>>T;
    while(T--){
        cin>>n;
        int a[n];
        for(int i=0;i<n;i++)
            cin>>a[i];
        bool flag = true;
        for(int i=2;i<n && flag;i++){
            l1 = min(a[i], a[i-1]);
            r1 = max(a[i], a[i-1]);
            for(int j=i-2;j>0;j--){
                l2 = min(a[j], a[j-1]);
                r2 = max(a[j], a[j-1]);
                if(F(l1, r1, l2, r2)){
                    flag = false;
                    break;
                }
            }
        }
        cout<<(flag?'n':'y')<<endl;
    }
    return 0;
}

""""
找到规律本题不难，对连续的3个值p1，p2，p3
若p3 落在p1、p2中间，则p1、p2区间两侧不能再取值用flag[]=False标记，
否则，p1、p2构成的区间内不能再取值。
by the way：
本题 -1000000 ≤ ai ≤ 1000000，对每一个整数设置并修改flag 时空复杂度较高，
所以通过排序好的b 只对经过的点设置flag，没有经过的点设置flag是没意义的。
"""
if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        n = int(input())
        a = list(map(int, input().strip().split()))
        if len(a) <= 3:
            print('n')
            continue
        b = sorted(a)
        
        flag = [True] * len(b)  # 所有点都可取
        ans = True  # 初始设为没有相交点
        p1, p2 = a[0], a[1]
        for i in range(2, len(a)):
            if flag[b.index(a[i])] == False:  # 判断此点是否在之前标记为不可取
                ans = False  # 存在一个相交点，即停止遍历并输出结果
                break
            if min(p1, p2) < a[i] < max(p1, p2):  # 更新区间外的flag为False
                for j in range(0, b.index(min(p1, p2))):
                    flag[j] = False
                for j in range(b.index(max(p1, p2)) + 1, len(b)):
                    flag[j] = False
            else:  # 更新区间内flag为False
                for j in range(b.index(min(p1, p2)) + 1, b.index((max(p1, p2)))):
                    flag[j] = False
            p1, p2 = p2, a[i]
        print('n' if ans else 'y')

	

while True:
    try:
        n = int(input())
        for case in range(n):
            m1 = int(input())
            list1 = list(map(int,input().split()))
            one = list()
            for i in range(len(list1)):
                if i <m1-1:
                    one.append((list1[i],list1[i+1]))
            count = 0
            flag = False
            #print(one)
            for i in one:
                k1,k2 = i[0],i[1]
                count+=1
                for j in range(count,len(one)):
                    ppp = one[j]
                    p1,p2 = ppp[0],ppp[1]
                    
                    if (min(k1,k2)<min(p1,p2) and max(k1,k2)>min(p1,p2) and max(k1,k2)<max(p1,p2))&nbs***bsp;(max(k1,k2)>max(p1,p2) and min(k1,k2)<max(p1,p2) and min(k1,k2)>min(p1,p2)):
                        flag =True
                        break
                else:
                    continue
                break
            if flag == True:
                print('y')
            else:
                print("n")
                        
        
    except:
        break

import java.util.*;
public class Main{
    private static final int COUNT=6;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int t=sc.nextInt();
            for(int i=0;i<t;i++){
                boolean bool=true;
                int n=sc.nextInt();
                TreeSet<Integer> set=new TreeSet<>();
                int a=sc.nextInt();
                set.add(a);
                for(int j=1;j<n;j++){
                    int b=sc.nextInt();
                    set.add(b);
                    int max=Math.max(a,b);
                    int min=Math.min(a,b);
                    if(bool&&(max!=set.higher(min))&&!(min==set.first()&&max==set.last())){
                        bool=false;
                    }
                    a=b;
                }
                if(bool)
                    System.out.println("n");
                else
                   System.out.println("y"); 
            }
        }
        sc.close();
    }
}

//没想到暴力也能解答  一直以为有优化的解法
#include<iostream>
(720)#include<vector>
#include<algorithm>

using namespace std;
bool judge(vector<int> &v){
    vector<vector<int>> cir;
    for (int i = 0; i < v.size()-1; i++){
        int L = min(v[i], v[i+1]);
        int R = max(v[i], v[i+1]);
        cir.push_back(vector<int> {L, R});
    }
    for (int i = 1; i < cir.size(); i++){
        for (int j = 0; j < i; j++){
            if (cir[i][0] < cir[j][0] && cir[i][1] < cir[j][1] && cir[i][1] > cir[j][0]){
                return true;
            }
            else if(cir[i][1] > cir[j][1] && cir[i][0] < cir[j][1] && cir[i][0] > cir[j][0]){
                return true;
            }
        }
    }
    return false;
}
int main(void){
    int T;
    cin>>T;
    vector<int> v;
    int n;
    int num;
    for (int i = 0; i < T; i++){
        cin>>n;
        if (n <= 2){
            cout<<"n"<<endl;
            continue;
        }
        v.clear();
        for (int j = 0; j < n; j++){
            cin>>num;
            v.push_back(num);
        }
        if (judge(v))
            cout<<"y"<<endl;
        else
            cout<<"n"<<endl;
    }
    return 0;
}

我已经尽量简化计算了，但只要有两层循环就超时😓