CCF 202012-2期末預測之最佳門檻值（字首和）

題目就不列了，說說思路：

定義的參數含義如下：

1、定義一個node清單arr，裡面包含y，實際結果result以及以這個y為門檻值預測正确個數right

2、定義一個int清單sum用于存字首和，字首和下标從1開始算比較友善，是以定義數組大小多1

3、定義一個y_last記錄前一個y，我們是排序後再操作的，而且每個門檻值隻計算一次，如果目前y跟y_last相等，那麼就跳過目前y，因為這個y已經作為門檻值被計算過了。

流程：

1、把輸入的值存進arr，然後按照y從小到大對arr排序

2、按照排序後的arr計算result的字首和sum，那麼sum[i]的含義就是排序後的第1個y到第i個y之間的實際結果為1的個數。

3、按照題目的意思，假設現在以yi為門檻值，那麼小于yi預測結果都為0，大于等于yi的預測結果為1。又因為我們對y排序了，是以我們隻需要知道這個yi之前實際為0的個數和這個yi及之後實際為1的個數

yi之前有i-1個數，其中實際為1的個數是sum[i-1]，是以實際為0的個數：(i - 1)-sum[i-1]

yi及之後實際為1的個數是總的實際為1的個數減去yi之前為1的個數：sum[m] - sum[i-1]

兩者相加即為正确個數

代碼如下：

#include <algorithm>
#include <iostream>
using namespace std;

struct node
{
    int y;
    int result;
    int right;
};

bool cmp(node s1, node s2)
{
    return s1.y < s2.y;
}

node arr[100001] = {0,0,0};
int  sum[100001] = {0};
int	 y_last = -1;

int main()
{
	int m,max_y=0,max_right=0;
	cin >> m;
	for(int i=1; i<=m; i++)
		cin >> arr[i].y >> arr[i].result;
	
	sort(arr+1,arr+m+1,cmp);
	
	//字首和 
	for(int i=1; i<=m; i++)
		sum[i] = arr[i].result + sum[i-1];
	
	//正确個數為前面結果為0的個數 + 自己以及後面預測為1的個數
	//如果y相同，隻考慮第一個y 
	for(int i=1; i<=m; i++)
		if(arr[i].y == y_last)
			continue;
		else{
			arr[i].right = (i-1-sum[i-1]) + (sum[m]-sum[i-1]);
			y_last = arr[i].y;
			if(arr[i].right >= max_right){
				max_right = arr[i].right;
				max_y = arr[i].y;
			}
		}
		
	cout << max_y;
}