[数据结构与算法]CCF CSP 202012-2 期末预测之最佳阈值 C++（100分）

#include<iostream>

using namespace std;

void quickSort(int a[], int b[], int start, int end) {  //start和end为数组始末下标
	if (start >= end)
		return;
	int mid = a[end];
	int left = start, right = end - 1;
	while (left < right) {  //在整个范围内搜寻比枢纽元值小或大的元素，然后将左侧元素与右侧元素交换
		while (a[left] < mid && left < right)  //试图在左侧找到一个比枢纽元更大的元素
			left++;
		while (a[right] >= mid && left < right) //试图在右侧找到一个比枢纽元更小的元素
			right--;
		swap(a[left], a[right]); //交换元素
		swap(b[left], b[right]);
	}
	if (a[left] >= a[end])
	{
		swap(a[left], a[end]);
		swap(b[left], b[end]);
	}
	else
		left++;
	quickSort(a, b, start, left - 1);
	quickSort(a, b, left + 1, end);
}
int main()
{
	int n;
	int One = 0;             //代表结果中1的个数
	int zero = 0;      //截止到b[i]时0的个数
	int number = 0;
	int max = 0;
	int temp = 0;
	cin >> n;
	int* a, * b, * c, * d, * e;
	a = new int[n];
	b = new int[n];
	c = new int[n];
	d = new int[n];//存储最大c[i]值的下标i
	for (int i = 0; i < n; i++)
	{
		cin >> a[i] >> b[i];
		c[i] = 0; d[i] = 0;
	}
	quickSort(a, b, 0, n - 1);
	for (int i = 0; i < n; i++)//先循环一遍，确定结果中1的个数
		if (b[i] == 1)
			One++;
	for (int i = 0; i < n; i++)
	{
		if (b[i] == 0)
		{
			c[i] = zero + One;
			zero++;
			if (i > 0 && a[i] == a[i - 1])
				c[i] = c[i - 1];
		}
		else
		{
			c[i] = One + zero;
			One--;
			if (i > 0 && a[i] == a[i - 1])
				c[i] = c[i - 1];
		}
	}
	for (int i = 0; i < n; i++)//找出最大的安全指数
	{
		if (max < c[i])
			max = c[i];
	}
	for (int i = 0; i < n; i++)//找出最大安全指数的个数,number的初始值为0
	{
		if (c[i] == max)
		{
			d[number] = i;
			number++;
		}
	}
	max = a[d[0]];
	for (int i = 0; i < number; i++)//找出最大安全指数对应的的最大的阈值
	{
		if (max < a[d[i]])
			max = a[d[i]];
	}
	cout << max << endl;
	delete[]a;
	delete[]b;
	delete[]c;
	delete[]d;
	return 0;
}

刚开始用的是冒泡排序，结果超时了，后来改成快速排序才通过。
先创建四个数组a,b,c,d，其中a数组存储y值，b数组存储result值，c,d数组初始化为0，然后用快速排序，将a数组从小到大排序（b数组亦然），然后发现每个c的值与当前b[i]值前面的0的个数以及b[i]之后1的个数的有关，且这两个数按规律变化，故可以利用这两个值快速计算。