水平线-研发

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

void Flood_Fighting() {
	int n = 0;//n个发电基站
	int q = 0;//q场洪水
	cin >> n;
	vector<pair<int,int>> power_station_height(n + 2);//存放每个发电基站的高度,n+2是为了防止下标越界，键值对，first用来保存发电站高度，second用来保存发电站位置

	for (int i = 1; i <= n; i++) {
		cin >> power_station_height[i].first;
		power_station_height[i].second = i;
	}

	cin >> q;
	vector<pair<int,int>> flood_height(q);//存放每场洪水的高度

	for (int i = 0; i < q; i++) {
		cin >> flood_height[i].first;
		flood_height[i].second = i;
	}

	vector<pair<int, int>> tmp(power_station_height);//临时数组,用于存放已排序的各发电站高度

	sort(tmp.begin() + 1, tmp.end() - 1);//对发电站高度排序
	sort(flood_height.begin(), flood_height.end());//对洪水高度排序

	vector<int> result(q, 0);//记录每次洪水过后的ans群数结果

	int r = 1;//用来记录上一次洪水淹没的最后一个发电站在tmp中的位置
	int count = 1;//因为洪水而分成的ans群数
	vector<int> sk(n + 2, 0);//状态数组，状态为0代表没有被淹，1代表被淹
	sk[0] = sk[n + 1] = 1;
	for (int i = 0; i < q; i++) {
		for ( int k = r ; k <= n; k++) {
			if (tmp[k].first <= flood_height[i].first) {
				sk[tmp[k].second] = 1;

				//每个沉下去的发电机有三种情况。
				//1. 两侧的发电机都沉下去了， 集群数 - 1;
				//2. 只有一侧的发电机沉下去， 集群数不变;
				//3. 两侧的发电机都未沉下去， 集群数 + 1.
				if (sk[tmp[k].second + 1] == 1 && sk[tmp[k].second - 1] == 1) {
					count--;
				}
				else if (sk[tmp[k].second + 1] != 1 && sk[tmp[k].second - 1] != 1) {
					count++;
				}

			}
			else {
				result[flood_height[i].second] = count;
				r = k;
				break;
			}
		}
	}

	for (auto e : result) {
		cout << e << endl;
	}
}

int main() {
	Flood_Fighting();
	return 0;
}

enb = int(input())
a_alti = [int(i) for i in input().split(" ")]
hx_t = int(input())
hx_h = [int(i) for i in input().split(" ")]
rsp_a = list(range(0, enb + 2))
rsp_a[0] = -1
rsp_a[enb + 1] = -1
hx_new_index = [index for index, value in sorted(enumerate(hx_h), key=lambda h: h[1])]
a_new_index = [index for index, value in sorted(enumerate(a_alti), key=lambda h: h[1])]
cluster_num = [0] * hx_t
k = 1
for i in range(hx_t):
    new_cluster = 0
    while k <= enb and a_alti[a_new_index[k-1]] <= hx_h[hx_new_index[i]]:
        if rsp_a[a_new_index[k-1]] == -1 and rsp_a[a_new_index[k-1]+2] == -1:
            new_cluster = new_cluster - 1
        elif rsp_a[a_new_index[k-1]] != -1 and rsp_a[a_new_index[k-1]+2] != -1:
            new_cluster = new_cluster + 1
        rsp_a[a_new_index[k-1]+1] = -1
        k = k + 1
    if i == 0:
        cluster_num[hx_new_index[i]] = 1 + new_cluster
    else:
        cluster_num[hx_new_index[i]] = cluster_num[hx_new_index[i - 1]] + new_cluster
for cn in cluster_num:
    print(cn)

等到两个数组后分别排序，基本逻辑就是海啸从低到高，电站海拔也从低到高，被低的海啸淹没的电站也一定被高的海啸淹没，
初始集群为1，没当一个电站淹没时，若左右均已淹没则集群数减一，左右均未被淹没时集群数加一，有一边被淹没时集群数不变

using System;

namespace NetEase
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());            
            string[] _a = Console.ReadLine().Split(' ');
            Gen[] a = new Gen[n];
            Gen[] a2 = new Gen[n];
            for (int i = 0; i < a.Length; i++)
            {
                a[i].height = a2[i].height = int.Parse(_a[i]);
                a[i].index = i;
                
            }
            Array.Sort(a);

            int q = int.Parse(Console.ReadLine());
            string[] _j = Console.ReadLine().Split(' ');
            Gen[] j = new Gen[q];
            for (int i = 0; i < j.Length; i++)
            {
                j[i].height = int.Parse(_j[i]);
                j[i].index = i;
            }
            Array.Sort(j);

            int[] results = new int[q];

            int index = 0;
            int result = 1;
            for (int i = 0; i < q; i++)
            {
                while (index < n && a[index] <= j[i])
                {
                    a2[a[index].index].sunk = true;
                    if ((a[index].index == 0 || a2[a[index].index - 1].sunk) && (a[index].index == n - 1 || a2[a[index].index + 1].sunk))
                    {
                        result--;
                    }
                    else if ((a[index].index != 0 && !a2[a[index].index - 1].sunk) && (a[index].index != n - 1 && !a2[a[index].index + 1].sunk))
                    {
                        result++;
                    }
                    index++;
                }
                results[j[i].index] = result;
            }

            foreach(int i in results)
            {
                Console.WriteLine(i);
            }
            Console.WriteLine();
        }
    }

    struct Gen : IComparable
    {
        public int height;
        public int index;
        public bool sunk;

        public int CompareTo(object obj)
        {
            return height.CompareTo(((Gen)obj).height);
        }
        public static bool operator <=(Gen a, Gen b)
        {
            return a.height <= b.height;
        }

        public static bool operator >=(Gen a, Gen b)
        {
            return a.height >= b.height;
        }
    }
}

Java不超时版本
加了快速输入输出才能过，要么T

import java.io.*;
import java.util.Scanner;


import java.lang.reflect.Array;
import java.util.*;

/**
 * @Author: Shang Huaipeng
 * @Date: 2020/4/1 14:36
 * @Version 1.0
 */
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try {
            StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
            sc.nextToken();
            int n = (int)sc.nval;
            int lo[][] = new int[n][2];
            for (int i = 0; i < n; i++) {
                sc.nextToken();
                lo[i][0] = (int)sc.nval;
                lo[i][1] = i + 1;
            }
            sc.nextToken();
            int m = (int)sc.nval;

            int yan[][] = new int[m][2];
            for (int i = 0; i < m; i++) {
                sc.nextToken();
                yan[i][0] = (int)sc.nval;
                yan[i][1] = i;
            }

            Arrays.sort(lo, (o1, o2) -> o1[0] - o2[0]);
            Arrays.sort(yan, (o1, o2) -> o1[0] - o2[0]);
            int ans[] = new int[m];
            boolean vis[] = new boolean[n + 2];
            int kuai = 1;
            int j = 0;
            vis[0] = vis[n + 1] = true;
            PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

            for (int i = 0; i < m; i++) {
                for (; j < n && lo[j][0] <= yan[i][0]; j++) {
                    vis[lo[j][1]] = true;
                    int tot = 0;
                    if (vis[lo[j][1] - 1]) tot++;
                    if (vis[lo[j][1] + 1]) tot++;
                    if (tot == 2) kuai--;
                    if (tot == 0) kuai++;

                }
                ans[yan[i][1]] = kuai;
            }
            for (int i = 0; i < m; i++) {
                out.println(ans[i]);
            }
            out.flush();
        }
        catch (Exception e){

        }
    }

}

#include <iostream>
#include <map>

using namespace std;


map<int,int> mp;
int jz[200010];
int n,m;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&jz[i]);
    }
    jz[0]=-100;
    jz[n+1]=-100;
    mp[-1]=1;
    int ptr=1;
    while(ptr<=n){
        bool l,r;
        l=jz[ptr]>jz[ptr-1];
        while(ptr<n&&jz[ptr]==jz[ptr+1]){
            ptr++;
        }
        r=jz[ptr]>jz[ptr+1];
        if(l&&r){
            mp[jz[ptr]]--;
        }else if(!l&&!r){
            mp[jz[ptr]]++;
        }
        ptr++;
    }
    int sum=0;
    int mx=0;
    for(auto itor=mp.begin();itor!=mp.end();++itor){
        sum+=itor->second;
        itor->second=sum;
        mx=itor->first;
    }
    scanf("%d",&m);
    while(m--){
        int tmp;
        scanf("%d",&tmp);
        if(tmp<0){
            printf("1\n");
            continue;
        }
        if(tmp>=mx){
            printf("0\n");
            continue;
        }
        printf("%d\n",(--mp.upper_bound(tmp))->second);
    }
}

n1 = int(input())
x = list(input().split())
n2 = int(input())
y = list(input().split())
for i in range(n2):
    l1 = []
    answer = 0
    gaodu = int(y[i])
    for j in range(n1):
        if int(x[j]) > gaodu:
                if j == n1-1:
                    answer += 1
                elif int(x[j+1])<= gaodu:
                    answer +=1
    print(answer)

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.solve(1, in, out);
        out.close();
    }

    static class Solver {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int[] altitudes = new int[n];
            for (int i = 0; i < n; ++i) {
                altitudes[i] = in.nextInt();
            }
            int q = in.nextInt();
            for (int i = 0; i < q; ++i) {
                out.println(countOfClusters(altitudes, in.nextInt()));
            }
        }

        private int countOfClusters(int[] altitudes, int floodAltitude) {
            int count = 0;
            if (altitudes[0] > floodAltitude) {
                count++;
            }
            for (int i = 1; i < altitudes.length; ++i) {
                if (altitudes[i] > floodAltitude && altitudes[i - 1] <= floodAltitude) {
                    count++;
                }
            }
            return count;
        }

    }
}