202012-2 期末预测之最佳阈值

/*暴力70*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int m;
struct point
{
  int y;
  int result;
} a[maxn];
int theta[maxn];
int cmp(point a1, point a2)
{
  if (a1.y < a2.y)
  {
    return true;
  }
  return false;
}
int main()
{
  cin >> m;
  for (int i = 1; i <= m; i++) // 选预测准确率最高的
  {
    cin >> a[i].y >> a[i].result;
  }
  int ans = 0;
  int ansnum = 0;
  sort(a + 1, a + 1 + m, cmp);
  for (int i = 1; i <= m; i++)
  { // 选第i个的y作为theta
    int sum = 0;
    for (int j = 1; j <= m; j++)
    { // 算正确次数
      if ((a[j].y >= a[i].y && a[j].result == 1) || (a[j].y < a[i].y && a[j].result == 0))
      {
        sum++;
      }
    }
    if (sum >= ansnum)
    {
      ans = a[i].y;
      ansnum = sum;
    }
  }
  cout << ans;
}

/*前缀和100*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int m;
struct point
{
  int y;
  int result;
} a[maxn];
int theta[maxn];
int cmp(point a1, point a2)
{
  if (a1.y < a2.y)
  {
    return true;
  }
  return false;
}
struct nn
{ // 每个theta 01个数前缀和
  int theta;
  int zero;
  int one;
} num[maxn];
int main()
{
  cin >> m;
  for (int i = 1; i <= m; i++) // 输入
  {
    cin >> a[i].y >> a[i].result;
  }
 
  sort(a + 1, a + 1 + m, cmp);//按从小到大对yi排序
  int uu = 1;//记录theta个数
  a[m + 1].y = a[m].y;
  a[m + 1].result = a[m].result;
  num[1].theta = a[1].y;
  for (int i = 1; i <= m; i++)
  {
    if (a[i].y != a[i + 1].y)
    {
      if (a[i].result == 1)
      {
        num[uu].one++;
      }
      else
      {
        num[uu].zero++;
      }
      uu++;
      num[uu].theta = a[i + 1].y;
      num[uu].zero += num[uu - 1].zero;
      num[uu].one += num[uu - 1].one; // 前缀和
    }
    else
    {
      if (a[i].result == 1)
      {
        num[uu].one++;
      }
      else
      {
        num[uu].zero++;
      }
    }
  }
  int ans = 0;
  int ansnum = 0;
  for (int i = 1; i <= uu; i++)
  { // 选第i个作为theta
    int sum = 0;
    if (i == 1)
    {
      sum = num[uu].one;
      if (sum >= ansnum)
      {
        ans = num[i].theta;
        ansnum=sum;
      }
    }
    else
    {
      //>=y:1
      sum +=num[uu].one-num[i-1].one;
      //<y:0
      sum+=num[i-1].zero;
      if (sum >= ansnum)
      {
        ans = num[i].theta;
        ansnum=sum;
      }
    }
  }
   cout << ans;
}