题目链接:题目链接
问题分析
通过分析题目我们可以发现问题可以转化为在yi中寻找一个θ,使得满足yi<θ时resulti为0的个数+满足yi≥θ时resulti为1的个数最大。如果有多个θ,则选取最大的θ输出即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
struct p
{
int y;
int result;
};
bool cmp(p& p1, p& p2)
{
if(p1.y != p2.y)
return p1.y < p2.y;
else
return p1.result < p2.result;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int dp0[100006] = {0},dp1[100005] = {0},count=0,m,max=-1,index=0;
p input[100005];
cin>>m;
for(int i=0;i<m;i++)
{
cin>>input[i].y>>input[i].result;
}
sort(input,input+m,cmp);
if(input[m-1].result == 1)
dp1[m-1] = 1;
if(input[0].result == 0)
count = 1;
for(int i=1;i<m;i++)
{
if(input[i].y != input[i-1].y)
{
dp0[i] = dp0[i-1] + count;
count = 0;
}
else
dp0[i] = dp0[i-1];
if(input[i].result == 0)
count++;
dp1[m-i-1] = dp1[m-i] + (input[m-i-1].result==1?1:0);
}
for(int i=0;i<m;i++)
{
if(max<=dp0[i] + dp1[i])
{
max = dp0[i]+dp1[i];
index = i;
}
}
cout<<input[index].y;
return 0;
}
前言 项目开发中不管是前台还是后台都会遇到烦人的null,数据库表中字段允许空值...
问题:我们在做flex的开发中,如果用到别人搭建好的框架,而别人的server名称往...
来源:DeepenStudy 漏洞文件:js.asp % Dimoblog setoblog=newclass_sys oblog.a...
本文转载自微信公众号「SH的全栈笔记」,作者SH。转载本文请联系SH的全栈笔记公...
idea官方推送了2020.2.4版本的更新,那么大家最关心的问题来了,之前激活idea202...
在Flash Player 10.1及以上版本中,adobe新增了全局错误处理程序UncaughtErrorEv...
CKeditor,以前叫FCKeditor,已经使用过好多年了,功能自然没的说。最近升级到3....
本文实例讲述了AJAX+Servlet实现的数据处理显示功能。分享给大家供大家参考,具...
大家好,我是狂聊君。 今天来聊一聊 Mysql 缓存池原理。 提纲附上,话不多说,直...
本文转载自微信公众号「SQL数据库」,作者丶平凡世界 。转载本文请联系开发公众...