codeforces 493 C Vasya and Basketball
2024-08-30 01:25:44
题意:给出三分线的值d,分别有两支队伍,如果小于等于d,得2分,如果大于d,得三分,问使得a-b最大时的a,b
一看到题目,就想当然的去二分了----啥都没分出来---55555555
后来才知道不能二分,因为随着d的增大,两个队的得分都会逐渐减少,但是两个队伍的得分的差值的单调性却不知道
是这一篇这样讲的 http://www.cnblogs.com/huangxf/p/4142760.html
然后就依次枚举d的值,维护一个最大值
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
using namespace std; typedef long long LL;
const int INF = (<<)-;
const int mod=;
const int maxn=; int n,m;
int a[maxn],b[maxn],c[maxn]; int main(){
int cnt=;
c[++cnt]=;
scanf("%d",&n);
for(int i=;i<n;i++) scanf("%d",&a[i]),c[++cnt]=a[i];
scanf("%d",&m);
for(int i=;i<m;i++) scanf("%d",&b[i]),c[++cnt]=b[i]; sort(a,a+n);
sort(b,b+m);
sort(c,c+cnt);
int tmp=-INF,L,R; int lb,ub;
for(int i=;i<=cnt;i++){
int x=upper_bound(a,a+n,c[i]) - a;
int y=upper_bound(b,b+m,c[i]) - b; lb = x* + (n-x)*;
ub = y* + (m-y)*;
if(lb - ub > tmp){
tmp=lb-ub;
L=lb;R=ub;
}
if(lb - ub == tmp && lb > L) L = lb;
}
printf("%d:%d\n",L,R);
return ;
}
最新文章
- 从DOM操作看Vue&;React的前端组件化,顺带补齐React的demo
- O365(世纪互联)SharePoint 之调查列表简单介绍
- Decorator实现AOP编程。
- 让div固定在顶部不随滚动条滚动
- web cache server方案比较:varnish、squid、nginx
- Log4j2常见使用示例及Syslog/Syslog-ng
- extjs 4.2 日期控件 选择时分秒功能
- Linux 中如何卸载已安装的软件
- VB6 GDI+ 入门教程[2] GDI+初始化
- Python 字典的创建赋值和动态扩展
- Linux中shell命令的用法和技巧
- HW3.14
- codevs1906 最长递增子序列问题
- 关于oracle数据库(1)
- Swift 内存管理详解
- Python之scrapy实例1
- gmock
- 知乎改版api接口之scrapy自动登陆
- 页面加载中jquery逐渐消失效果实现
- svn导出历史版本