博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Codeforces 493C - Vasya and Basketball
阅读量:7291 次
发布时间:2019-06-30

本文共 4393 字,大约阅读时间需要 14 分钟。

C. Vasya and Basketball
题目链接:
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Vasya follows a basketball game and marks the distances from which each team makes a throw. He knows that each successful throw has value of either 2 or 3 points. A throw is worth 2 points if the distance it was made from doesn't exceed some value of d meters, and a throw is worth 3 points if the distance is larger than d meters, where d is some non-negative integer.

Vasya would like the advantage of the points scored by the first team (the points of the first team minus the points of the second team) to be maximum. For that he can mentally choose the value of d. Help him to do that.

Input

The first line contains integer n (1 ≤ n ≤ 2·105) — the number of throws of the first team. Then follow n integer numbers — the distances of throws ai (1 ≤ ai ≤ 2·109).

Then follows number m (1 ≤ m ≤ 2·105) — the number of the throws of the second team. Then follow m integer numbers — the distances of throws of bi (1 ≤ bi ≤ 2·109).

Output

Print two numbers in the format a:b — the score that is possible considering the problem conditions where the result of subtraction a - b is maximum. If there are several such scores, find the one in which number a is maximum.

Examples
input
3 1 2 3 2 5 6
output
9:6
input
5 6 7 8 9 10 5 1 2 3 4 5
output
15:10 题目大意:找一个三分线d(大于d得3分,小于等于d得2分),使得第一支队伍得分减去第二只队伍得分(a-b)最大,并且输出a:b;如果有好几组答案,输出a最大的那组答案。 方法一: 将两只队伍的距离保存到一个数组c[]中,然后从c[]中枚举出三分线d,求出最大的(a-b),同时记录a和b。(在代码中x表示a,y表示b) 注意:注意边界,不然不能ac,下面以两个不同代码为例: 代码1:
#include
#include
#include
using namespace std;const int N=200000;int a[N],b[N],c[2*N];int main(){ int n,m,cnt=1; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; c[cnt++]=a[i]; } cin>>m; for(int i=1;i<=m;i++) { cin>>b[i]; c[cnt++]=b[i]; } sort(a+1,a+n+1); sort(b+1,b+m+1); sort(c+1,c+cnt); int ans ; int x, y; x = n * 2; y = m * 2; ans = x - y;//上边界(相当于代码2中的c[cnt-1]),是三分线d大于等于c[]最大值的情况,所以两队所有距离都只能得2分 for(int i=cnt-2;i>=0;i--)//所以这里从cnt-2开始,不过从cnt-1开始也可以ac {
//下边界是c[0]=0,比所有距离都小,所以两队所有距离都得3分 int temp1=upper_bound(a+1,a+n+1,c[i])-a-1; int temp2=upper_bound(b+1,b+m+1,c[i])-b-1; if(ans<=temp1*2+(n-temp1)*3-temp2*2-(m-temp2)*3) { x=temp1*2+(n-temp1)*3; y=temp2*2+(m-temp2)*3; ans=x-y; } } cout<
<<":"<
<

代码2:

#include
#include
#include
using namespace std;const int N=200000;const int INF=0x3f3f3f3f; int a[N],b[N],c[2*N];int main(){ int n,m,cnt=1; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; c[cnt++]=a[i]; } cin>>m; for(int i=1;i<=m;i++) { cin>>b[i]; c[cnt++]=b[i]; } sort(a+1,a+n+1); sort(b+1,b+m+1); sort(c+1,c+cnt); int ans; int x, y; x = -INF; y = INF; ans = x - y; //初始值不赋值为上边界,赋值成负无穷 for(int i=cnt-1;i>=0;i--)//这里的上边界是c[cnt-1] {
//下边界是c[0]=0,比所有距离都小,所以两队所有距离都得3分 int temp1=upper_bound(a+1,a+n+1,c[i])-a-1; int temp2=upper_bound(b+1,b+m+1,c[i])-b-1; if(ans<=temp1*2+(n-temp1)*3-temp2*2-(m-temp2)*3) { x=temp1*2+(n-temp1)*3; y=temp2*2+(m-temp2)*3; ans=x-y; } } cout<
<<":"<
<

 方法二:与方法一差不多,不过是从a[]中枚举出三分线d,还有是用循环(而没有用upper_bound()这个函数)来找三分球个数。

代码3:

#include
#include
#include
using namespace std;const int N=200000+5;int a[N];int b[N];int main(){ int n,m; cin>>n; for(int i=0;i
>a[i]; cin>>m; for(int i=0;i
>b[i]; sort(a,a+n); sort(b,b+m); int j=m-1; int ab=n,ba=m; int x=0,y=0;//x代表一队三分球个数,y代表二队三分球个数 for(int i=n-1;i>=0;i--) { while(j>=0&&a[i]<=b[j]) { j--; y++; } x++; if(x-y>=ab-ba) { ab=x; ba=y; } } if(ab

 

 

转载于:https://www.cnblogs.com/widsom/p/6714657.html

你可能感兴趣的文章
前端面试总结
查看>>
<script type="text/template">是干什么的,为什么要把html写在js中? 这是什么编程语言风格,都能这样用吗?...
查看>>
hdu2196(树形dp)
查看>>
编辑框CEdit自动换行简单设置
查看>>
华为实习日记——第十九天
查看>>
awk用法小结
查看>>
你有没有忽略TextField的leftView这个属性
查看>>
A和B两个数组,删除B中与A重复的元素
查看>>
方格广搜
查看>>
match
查看>>
今日工作情况2
查看>>
一个学习简单网络技术的网站
查看>>
使用JQuery的get或post方法时出现页面没法手动刷新?
查看>>
MongoDB进阶
查看>>
python3csv与xlsx文件操作模块(csv、xlsxwriter)
查看>>
开启线程方式
查看>>
xdebug
查看>>
Css之 间距初始化
查看>>
lsnrctl启动报错,Linux Error: 29: Illegal seek
查看>>
IDEA github
查看>>