首页 > 试题广场 >

知识竞赛

[编程题]知识竞赛

热度指数：2307 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

最近部门要选两个员工去参加一个需要合作的知识竞赛，每个员工均有一个推理能力值 $A_{i}$ ，以及一个阅读能力值 $B_{i}$ 。如果选择第 $\mathit i$ 个人和第 $\mathit j$ 个人去参加竞赛，那么他们在阅读方面所表现出的能力为 $X=\frac{(B_{i}+B_{j})}{2}$ ，他们在推理方面所表现出的能力为 $Y=\frac{(A_{i}+A_{j})}{2}$ 。

现在需要最大化他们表现较差一方面的能力，即让 $\mathit min(X,Y)$ 尽可能大，问这个值最大是多少。

进阶：时间复杂度 $O(nlogn)\$ ，空间复杂度 $O(n)\$

输入描述:

第一行一个正整数 ，代表员工数。
接下来  行每行两个正整数 ，分别用来描述第  个员工的推理和阅读能力。

输出描述:

仅一行一个一位小数用来表示答案。

示例1

输入

输出

2.0

说明

选择第一个和第二个员工或第一个和第三个时，较差方面的能力都是 ，选择第二个和第三个时较差方面能力是 。

算法知识视频讲解

kyzheng

Python版本，算法复杂度过大，供参考

n = int(input())
a = [[] for i in range(n)]

for i in range(n):
    a[i] = input().split()

for i in range(n):
    for j in range(len(a[i])):
        a[i][j] = int(a[i][j])

m_min = []

for i in range(n-1):
    for j in range(i+1, n):
        m1 = (a[i][0] + a[j][0]) / 2
        m2 = (a[i][1] + a[j][1]) / 2
        m_min.append(min(m1, m2))

print(max(m_min))

发表于 2022-03-19 11:40:50 回复(0)

牛客555793294号

将员工的两项能力值之差的绝对值|ai-bi|由小到大排序，那么较差的能力是A还是B肯定是由排在后面的员工决定的。用后面员工的较弱能力（A或者B）跟当前该项能力的最大值相加，然后和当前记录的最大弱项和值比较就OK了。

import java.util.*;

public class Main
{

public static int arr[][];
public static int maxX,maxY;
public static int maxMin;
public static double res;
public static int n;
public static void main(String[]args)
{
Scanner scan=new Scanner(System.in);
n=scan.nextInt();

arr=new int[n][2];
for(int i=0;i<n;i++)
{
arr[i][0]=scan.nextInt();
arr[i][1]=scan.nextInt();
}
Arrays.sort(arr,new Comparator<int[]>() {
    @Override
    public int compare(int[]o1,int[]o2)
    {
        return Math.abs(o1[0]-o1[1])-Math.abs(o2[0]-o2[1]);
    }
});
maxX=arr[0][0];
maxY=arr[0][1];

for(int i=1;i<n;i++)
{
     int current;
     if(arr[i][0]>arr[i][1])
     current=arr[i][1]+maxY;
else
     current=arr[i][0]+maxX;
     if(current>maxMin)
         maxMin=current;
     maxX=Math.max(arr[i][0], maxX);
     maxY=Math.max(arr[i][1], maxY);
}

res=maxMin/2.0;

System.out.println(res);
}

}

发表于 2021-06-12 19:26:57 回复(9)

牛客692827558号

先按把数据按Ai排序，然后从最后一项开始，选一项和剩下的项一一匹配，匹配过程从后往前：先选最后一项，和倒数第二项匹配，然后倒数第三项。。。依次往前，每次匹配判断Bi的和是否大于Ai的和，如果大于则终止（因为Ai是排好序的，所以再往前的匹配劣于当前匹配）。匹配完了再选倒数第二项和剩下项匹配。。。。匹配过程顺便记录最大弱项值即可。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> dat(n);
    for(int i = 0; i < n; i++)
        cin >> dat[i].first >> dat[i].second;
    sort(dat.begin(), dat.end(), [](const pair<int, int> &a, const pair<int, int> &b)
         {
             if(a.first == b.first)
                 return a.second < b.second;
             return a.first < b.first;
         });
    int s = 0, cmax = 0;
    for(int cur = n - 1; cur >= s; cur--)
    {
        int cA = dat[cur].first;
        int cB = dat[cur].second;
        for(int i = cur - 1; i >= s; i--)
        {
            if(dat[i].second + cB >= dat[i].first + cA)
            {
                cmax = max(cmax, dat[i].first + cA);
                s = i;
                break;
            }
            cmax = max(cmax, dat[i].second + cB);
        }
    }
    cout << cmax/2.0;
    return 0;
}

发表于 2022-03-26 17:05:50 回复(0)

寒冰-侠客

先把数据按Ai排序，然后二分答案mid。依次检查第i个元素能否在其后的元素i+1.....n之中找到满足条件的组合。

先用lowerbound找到A值满足要求的第一个元素下标t，检查这个元素之后的所有元素中是否有B值能和Bi组合满足mid条件。

此处用一个后缀最大值数组来存储某元素之后的最大值。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct node
{
    int x,y;
    bool operator<(const node B)const
    {
        return x<B.x;
    }
}a[200005];
int n,b[200005],maxv[200005];
bool check(int x)
{
    for(int i=1;i<=n;i++)
    {   /**< 在i之后找到能和a[i].x的和满足要求的位置 */
        node temp={x-a[i].x,0};
        int t=lower_bound(a+i+1,a+n+1,temp)-a;
        if(t==n+1)
            continue;/**< 显然t之后的x都满足要求，那么最大的y是否满足要求？ */
        if(a[i].y+maxv[t]>=x)
            return true;
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1);
    for(i=n;i>=1;i--)/**< 后缀数组存储最大值 */
        maxv[i]=max(maxv[i+1],a[i].y);
    int l=0,r=1e9,mid,best=0;
    while(l<=r)
    {
        mid=l+r>>1;
        if(check(mid))
         best=mid,l=mid+1;
        else
            r=mid-1;
    }
    printf("%.1f",best/2.0);
    return 0;
}

发表于 2021-05-02 17:40:17 回复(1)

Python

programgirl

while True:
try:
n = int(input().strip())
info = []
for i in range(n):
L = list(map(int, input().strip().split()))
info.append(L)
info.sort(key=lambda x: x[0], reverse=True)
max_mean = min(info[0][0] + info[1][0], info[0][1] + info[1][1])
store = [0, 1]
if info[0][1] + info[1][1] > info[0][0] + info[1][0]:
print((info[0][0] + info[1][0]) / 2)
else:
for i in range(2, len(info)):
if info[i][1] < min(info[store[0]][1], info[store[1]][1]):
continue
else:
A = min(info[store[0]][0] + info[i][0], info[store[0]][1] + info[i][1])
B = min(info[store[1]][0] + info[i][0], info[store[1]][1] + info[i][1])
if A > max_mean:
store[0] = i
max_mean = A
elif B > max_mean:
store[1] = i
max_mean = B
else:
continue
print(max_mean / 2)

except EOFError:
break

发表于 2022-09-25 22:00:32 回复(0)

heng-star

简单遍历

为什么这样也行

有没有变态的例子来测试一下。

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        int n=Integer.parseInt(scanner.nextLine());
        PriorityQueue<double[]> q=new  PriorityQueue<>((a1,b) -> {
            double x=(a1[0]+ a1[1]);
            double y=(b[0]+b[1]);
            if(x>y){ return -1;}
            else{return 1;}
        });
        for(int i=0;i<n;i++){
            String[] s=scanner.nextLine().split(" ");
            q.offer(new double []{Integer.parseInt(s[0]),Integer.parseInt(s[1])});           
        }       
        double p1[]=q.poll();
        double p2[]=q.poll();
        double min=0;
        while (q.size()>0){
            if(min<Math.min((p1[1]+p2[1])/2.0,(p1[0]+p1[0])/2.0)){
                min=Math.min((p1[1]+p2[1])/2.0,(p1[0]+p1[0])/2.0);
            }
            p1=p2;
            p2=q.poll();
        }
        System.out.println(min);
    }    
}

发表于 2022-04-15 17:13:25 回复(0)

Syz_cannot

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

bool cmp(pair<int,int> &a,pair<int,int> &b){
    if (a.first==b.first) return a.second>b.second;
    return a.first<b.first;
}
int main() {
    int n;
    cin>>n;
    vector<pair<int,int>> person(n);
    for (int i=0;i<n;i++){
        cin>>person[i].first>>person[i].second;
    }
    sort(person.begin(),person.end(),cmp);
    stack<int> st;
    st.push(0);
    int ansx=person[0].first; int ansy=person[0].second; int ans=0;
    for (int i=1;i<n-1;i++){
        ans=max(ans,min(person[st.top()].first+person[i].first,person[st.top()].second+person[i].second));
        while (!st.empty()&&person[st.top()].second<person[i].second){
            st.pop();
        }
        st.push(i);
    }
    int i=n-1;
    while (!st.empty()){
        ans=max(ans,min(person[st.top()].first+person[i].first,person[st.top()].second+person[i].second));
        st.pop();
    }
    double fin=ans/2.0;
    cout<<setiosflags(ios::fixed)<<setprecision(1)<<fin;
    return 0;
}

可以按照a排序之后用单调栈维护

发表于 2022-03-17 22:21:27 回复(0)

onestan

#include <bits/stdc++.h>

using namespace std;

int main()

{

int n;

cin>>n;

pair<int, int> *m1=new pair<int, int>[n];

for(int i=0;i<n;++i)

{

cin>>m1[i].first>>m1[i].second;

}

sort(m1, m1+n);

vector<pair<int, int>> m;

int minskill=0;

for(int i=0;i<n-1;++i)

{

if(m1[i].first!=m1[i+1].first)

{

if(m.empty()||m1[i].second<m.back().second) m.push_back(m1[i]);

else

{

minskill=max(minskill,min(m1[i].first+m.back().first,m1[i].second+m.back().second));

m.back()=m1[i];

}

m.push_back(m1[n-1]);

n=m.size();

if(n==1) minskill=max(m[0].first,m[0].second)*2;

for(int i=0;i<n;++i)

for(int j=n-1;j>i;--j)

{

minskill=max(minskill,min(m[i].first+m[j].first,m[i].second+m[j].second));

if(m[i].first+m[j].first<=m[i].second+m[j].second)break;

}

cout<<(double)minskill/2;

return 0;

}

发表于 2021-09-01 13:08:59 回复(0)

JCoder

二分答案套双指针查找带后缀数组优化

发表于 2021-08-13 16:07:36 回复(0)

Python

yyyywwwwqqqq

n = int(input())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
res = 0
ab.sort(key = lambda x:abs(x[1]-x[0]))
maxa = ab[0][0]
maxb = ab[0][1]
for a,b in ab:
    if a>b:
        res = max((b+maxb)/2,res)
    else:
        res = max((a+maxa)/2,res)
    if a>maxa:
        maxa = a
    if b>maxb:
        maxb = b
print(res)

根据第一的思路加个python版本

发表于 2021-07-30 10:35:08 回复(2)

Dominic789654

用例:
3
4 100
50 50
10000 10000
代码实际输出：
5025.0
你期望的输出：

10050.0

这个例子是错误的吧

发表于 2021-06-20 16:46:09 回复(1)

牛客648304865号

直接遍历时间复杂度超了，改了一下遍历的终止条件。

先把数据按A+B降序排列，然后将终止条件改为A[i]+B[i]+A[j]+B[j]<=4*当前最大的min(X,Y)，然后就能过了

C语言的

#include <stdio.h>
#include <stdlib.h>
int cmp (const void * a, const void * b)
{
    int * p1 = (int *) a;
    int * p2 = (int *) b;

   return ( *p2+*(p2+1)-*p1-*(p1+1) );
}
int main(void){
    int n;
    scanf("%d",&n);
    int A[n][2];
    for (int i=0;i<n;i++){
        scanf("%d %d",&A[i][0],&A[i][1]);
    }
    qsort(A,n, sizeof(A[0]),cmp);
    int minone=0;
    int maxminone=minone;
    int du,tui;
    for (int i=0;i<n;i++){
        int j=i+1;
        while(A[i][0]+A[j][0]+A[i][1]+A[j][1]>2*maxminone){
            du=(A[i][0]+A[j][0]);
            tui=(A[i][1]+A[j][1]);
            if(du<tui){
                minone=du;
            }
            else{
                minone=tui;
            }
            if(minone>maxminone){
                maxminone=minone;
            }
            j++;
        }
    }
    float result=maxminone/2.0;
    printf("%.1f",result);
    
    return 0;
}

发表于 2021-05-30 21:58:40 回复(0)

提交观点

问题信息

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师阿里巴巴测试工程师 PHP工程师安全工程师游戏研发工程师 2021 数据库工程师信息技术岗区块链测试开发工程师大数据开发工程师数据分析师 Java工程师

上传者：小小

难度：

12条回答 105收藏 7403浏览

通过挑战的用户

查看代码

古巴比伦王

2023-03-14 19:43:35
o0ffice

2023-03-14 17:13:56
牛客90130...

2022-12-02 19:29:44
牛客62575...

2022-11-17 14:28:47
懒羊羊不能再懒了

2022-10-29 13:52:00