首页 > 试题广场 >

组队竞赛

[编程题]组队竞赛
  • 热度指数：11118 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
牛牛举办了一次编程比赛,参加比赛的有3*n个选手,每个选手都有一个水平值a_i.现在要将这些选手进行组队,一共组成n个队伍,即每个队伍3人.牛牛发现队伍的水平值等于该队伍队员中第二高水平值。
例如:
一个队伍三个队员的水平值分别是3,3,3.那么队伍的水平值是3
一个队伍三个队员的水平值分别是3,2,3.那么队伍的水平值是3
一个队伍三个队员的水平值分别是1,5,2.那么队伍的水平值是2
为了让比赛更有看点,牛牛想安排队伍使所有队伍的水平值总和最大。
如样例所示:
如果牛牛把6个队员划分到两个队伍
如果方案为:
team1:{1,2,5}, team2:{5,5,8}, 这时候水平值总和为7.
而如果方案为:
team1:{2,5,8}, team2:{1,5,5}, 这时候水平值总和为10.
没有比总和为10更大的方案,所以输出10.

输入描述:
输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)

第二行包括3*n个整数a_i(1 ≤ a_i ≤ 10^9),表示每个参赛选手的水平值.


输出描述:
输出一个整数表示所有队伍的水平值总和最大值.
示例1

输入

2
5 2 8 5 1 5

输出

10
算法知识视频讲解
添加回答
Alex_zmx头像 Alex_zmx 

	importjava.util.Arrays;





	importjava.util.Scanner;





	





	
	

		/**
	


	

		* Created by 张明旭 on 2017/5/19.
	


	

		* 思路是这样的 先排序
	


	

		* 比如排完序 1 2 3 4 5 6 7 8 9 这九个数
	


	

		* 组队思路是这样的 第一个最后两个 1 8 9
	


	

		* 剩下 2 3 4 5 6 7
	


	

		* 第一个最后两个                 2 6 7
	


	

		* 剩下                           3 4 5
	


	

		* 就是第一个和最后两个 再把已经组队的删掉 然后在循环 第一个最后两个
	


	

		* 那么中位数可以看到是 8 6 4
	


	

		* 找到中位数在整个排序后的素组和下标的规则是 data[data.length-(2*(i+1))]
	


	

		* 再加在一起
	


	

		* 最重要的是 result一定要是long的 一定 一定 int会越界
	


	

		*/
	







	public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n;
        long[] data;
        while(scanner.hasNext()){
            n=scanner.nextInt();
            data = new long[3*n];
            for (int i = 0; i <data.length ; i++) {
                data[i] = scanner.nextLong();
            }
            Arrays.sort(data);
            long result = 0;
            for (int i = 0; i < n; i++) {
                result+=data[data.length-(2*(i+1))];
            }
            System.out.println(result);
        }
    }
}

编辑于 2017-05-19 21:42:09 回复(5)
C/C++
pein531头像 pein531

贪心

先将所有人的水平按升序排列，每次选择当前剩余的人之中，水平最高的两个人和水平最低的一个人组队，这样就能最大化团队水平中位数的值。 
#include <bits/stdc++.h>
using namespace std;

const int N = 300010;
int n, a[N];

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < 3*n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a + 3*n);
    long long ans = 0;
    int strong = 3*n - 1, cnt = 0;
    while(cnt < n) {
        ans += a[strong - 1];
        strong -= 2;
        cnt++;
    }
    printf("%lld", ans);
    return 0;
}

发表于 2023-02-02 17:45:46 回复(0)
colining头像 colining
有没有和我一样因为sum 不是long ，所以通过率只有60%的人啊 ：(
发表于 2017-05-20 20:59:19 回复(4)
wanglian头像 wanglian 
  #include<iostream> 
  #include<vector> 
  #include<algorithm> 
  using namespace std; 
  

  

  long helper(vector<int>& v,int n){ 
      long sum=0; 
      sort(v.begin(),v.end()); 
      for(int i=n;i<3*n;i+=2){ 
          sum += v[i]; 
      } 
      return sum; 
  } 
  

  

  int main(){ 
      int n,t; 
      long sum=0; 
      vector<int> v; 
      cin>>n; 
      for(int i=0;i<3*n;i++){ 
          cin>>t; 
          v.push_back(t); 
      } 
      cout<<helper(v,n)<<endl; 
      return 0; 
  }
编辑于 2018-01-30 14:53:34 回复(4)
C/C++
垚瞐头像 垚瞐 
#include<stdio.h>
void quick_sort(int* s,int l,int r)
{
    if(l<r)
    {
        int i=l,j=r,x=s[l];
        while(i<j)
        {
            while(i<j&&s[j]>=x)
                j--;
            if(i<j)
                s[i++]=s[j];
            while(i<j&&s[i]<x)
                i++;
            if(i<j)
                s[j--]=s[i];
        }
        s[i]=x;
        quick_sort(s,l,i-1);
        quick_sort(s,i+1,r);
    }
}
int main()
{
    int n=0;
    long sum=0;
    scanf("%d",&n);
    getchar();
    int all=3*n;
    int*arr=(int*)malloc(sizeof(int)*all);
    for(int i=0;i<all;i++)
    {
        scanf("%d",&arr[i]);
        getchar();
    }
    quick_sort(arr,0,all-1);
    int index = n;
    for (int i = 0; i < n; i++)
    {
        sum = sum + arr[index];
        index += 2;
    }
    
    printf("%ld\n",sum);
}

发表于 2022-07-25 19:15:57 回复(0)
牛客618919098号头像 牛客618919098号 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        ArrayList<Long> arr = new ArrayList<>();
        List<Long> list=new ArrayList<>();
        for (int i = 0; i < 3*n; i++) {
            arr.add(scan.nextLong());
        }
        Collections.sort(arr);
        list=arr.subList(n,3*n);
        long sum=0;
        for(int i=0;i<list.size();i++){
            if(i%2==0){
                sum+=list.get(i);
            }
        }
        System.out.println(sum);
    }
}

发表于 2022-05-13 17:55:52 回复(0)
SuRe28头像 SuRe28
把数组定义在while外面，就不会内存超限 
import java.util.Arrays;
import java.util.Scanner;

public class Main {

     public static void main(String[] args) {
          Scanner input = new Scanner(System.in);
          int a[] = new int[300000];
          while (input.hasNext()) {
               int n = input.nextInt();
               for (int i = 0; i < n * 3; i++) {
                    a[i] = input.nextInt();
               }
               Arrays.sort(a, 0, 3 * n);
               int end = 3 * n - 1;
               int begin = 0;
               long sum = 0;
               while (end > begin) {
                    sum = sum + a[end - 1];
                    end = end - 2;
                    begin = begin + 1;
               }
               System.out.println(sum);
          }
     }
}
发表于 2017-09-19 15:37:13 回复(1)
梦向南头像 梦向南 
  #include<vector> 
  #include<iostream> 
  #include<algorithm> 
  using namespace std; 
  

  long long MaxSum(vector<long long> &arr, int N) 
  { 
  long long sum = 0; 
  sort(arr.begin(), arr.end()); 
  for (int i = 0; i < N / 3; i++) 
  sum += arr[N - 2 - 2 * i]; 
  return sum; 
  } 
  

  int main() 
  { 
  int n; 
  cin >> n; 
  vector<long long> str; 
  for (int i = 0, tep; i < 3 * n; i++) 
  { 
          cin>>tep; 
          str.push_back(tep); 
      } 
  cout << MaxSum(str, 3 * n) << endl; 
  return 0; 
  }
编辑于 2018-01-30 14:53:47 回复(0)
不能让人知道我是谁头像 不能让人知道我是谁
importjava.util.*;
 
publicclassMain{
     
    publicstaticvoidmain(String[] args){
         
        Scanner input = newScanner(System.in);
        while(input.hasNext()){
            intn = input.nextInt();
            int[] a = newint[n*3];
            for(inti=0; i<n*3;i++){
                a[i] = input.nextInt();
            }
            Arrays.sort(a);
            longsum = 0;
            for(inti=n; i<n*3;i = i+2){
                sum += a[i];
            }
            System.out.println(sum);
        }
    } 
}

实在是弄不明白为何会内存溢出
发表于 2017-06-11 16:40:09 回复(2)
yudw1316头像 yudw1316 
#include <iostream>



#include <cstring>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <iterator>
#include <set>
using namespace std;
int main()
{
    int n;
    vector<int64_t> a;
    while(cin>>n)
    {
        a.resize(3*n);
        for(int i=0; i<3*n; i++)
        {
            cin>>a[i];
        }
        std::sort(a.begin(), a.end());
        int64_t maxNum = 0;
        for(int i=3*n-2, k=0; k<n; i-=2,k++)
        {
            maxNum += a[i];
        }
        cout<<maxNum<<endl;
    }
    return 0;
}

发表于 2017-05-30 09:23:35 回复(0)
八歌头像 八歌 
/**
* 原先想的太复杂了，这题原来这么简单。。
* 排序，然后取 第 3n - 1  3n - 3  3n - 5...个元素累加即可
* 例如 现在排序后 有 1  2  5  5  8  9  ，那么取  8 和 5相加等于 13 
* 我们每次尽量取最大，但是最大的数不可能是中位数，所以退而求其次，取 每组中第二大的
*/
import java.util.Scanner;
import java.util.Arrays;

public class Main{
	public static void main(String args[]){
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()){
			int n = scan.nextInt();
			int[] arr = new int[3*n];
			for(int i = 0; i < 3*n; i++){
				arr[i] = scan.nextInt();
			}
			Arrays.sort(arr);
			long sum = 0;
			for(int i = 3*n - 2;i >= n; i -= 2){
				sum += arr[i];
			}
			System.out.println(sum);			
		}
	}
}

发表于 2017-05-22 20:03:48 回复(1)
偶尔刷刷题~头像 偶尔刷刷题~ 
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
	Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] x = new int[3*n];
        for(int i=0;i<3*n;i++)
        {
          x[i]=in.nextInt();
        }
        Arrays.sort(x); 
        long sum = 0;
        int i=x.length-2;
        while(i>=n-1)          	  
        {   
          sum = sum+x[i]; 
          i = i-2;
        }   
        System.out.println(sum);
	}

}

发表于 2017-05-19 21:17:04 回复(1)
ManTou_Chen头像 ManTou_Chen
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n = 0;
    while (cin >> n) {
        long long sum = 0;
        vector<int> a; //存放数据
        a.resize(3 * n); //初始化数据，开空间

        for (int i = 0; i < (3 * n); i++) {
            cin>>a[i];
        }

        //排序 -- 默认：升序
        sort(a.begin(),a.end());

        //使用贪心；每一组取到第二大的值
        //六个数里面，不论排序如何，都是两第二大的值相加为最优解
        //5 2 8 5 1 5 =》 125558
       for(int i=0;i<n;i++)
       {
            //每一组第二大值的累加
            sum += a[a.size()-(2*(i+1))];
            //a.size() => 6
            //6-2*(0+1) =4; //a[4]=5
            //6-2*(1+1) =2; //5[2]=5

            //为什么是：a.size()-(2*(i+1))
            //因为六个数经过排序；且需要找到到每组中两个第二大值的下标
            //也就是取六个数的第三个和第五个；
            //1 2 5 5 5 8
            //2 3 6 7 8 9
                    _    _
            //这样的到的，和一定会是最大的
           

       }
       printf("%lld",sum);
    }

}
// 64 位输出请用 printf(\"%lld\")
发表于 2024-01-22 14:17:01 回复(0)
神码_头像 神码_ 
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    int n;
    cin>>n;
    vector<int> v1;
    v1.resize(3*n);
    for(size_t i=0;i<3*n;i++)
    {
        cin>>v1[i];
    }
    sort(v1.begin(),v1.end());
    long long sum=0;
    int len=v1.size();
    for(size_t i=0;i<n;i++)
    {
        sum+=v1[len-2*(i+1)];
    }
    cout<<sum;

}
// 64 位输出请用 printf("%lld")

发表于 2023-09-23 21:57:30 回复(0)
Java
风度翩翩的单身狗很热情头像 风度翩翩的单身狗很热情
import java.util.Scanner;
import java.util.Arrays;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();
       int[] num = new int[3*n];
       for(int i=0;i<3*n;i++) {
        num[i] = sc.nextInt();
       }
       Arrays.sort(num);
       long res = 0;
       for(int i=0;n+2*i<3*n;i++) {
        res += num[n+2*i];
       }
       System.out.println(res);
    }
}
发表于 2023-09-14 22:42:08 回复(0)
石灰石的泡沫头像 石灰石的泡沫
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>

long getMax() {
    int n = 0;
    cin >> n;
    vector<int> arr(3 * n);
    for (int i = 0; i < 3 * n; i++) {
        cin >> arr[i];
    }
    //将数组排序
    std::sort(arr.begin(), arr.end());
    long ret = 0;
    for (int i = n; i < 3 * n; i += 2) {
        ret += arr[i];
    }

    return ret;
}

int main() {
    cout << getMax() << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")
发表于 2023-07-30 10:15:41 回复(0)
牛客788393123号头像 牛客788393123号
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
        int num;
        while(cin>>num)
        {
            long long sum = 0;
            vector<int> a;
            a.resize(3*num);
            for(size_t i= 0; i<(3*num);i++ )
            {
                cin>>a[i];
            }
            sort(a.begin(),a.end());
            //排序后取最大的两个数和最小的一个数为一组是局部最优解
            for(size_t i = 0; i<num;i++)
            {
                sum+= a[a.size() - (2*(1+i))];
            }
            cout<< sum<<endl;
            return 0;
        }
    }
发表于 2023-05-06 18:06:47 回复(0)
薯条和番茄酱头像 薯条和番茄酱 

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author zq
 * 组队竞赛
 */
public class day1_1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();//n代表分几组
        int[] arr = new int[n*3];
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            for (int i = 0; i < arr.length; i++) {
                arr[i] = in.nextInt();
            }
            Arrays.sort(arr);//将取到的数组排序
            int sum =0;
            //遍历数组，找到最大的中间值，相加
            //此时由于是三个一组，所以分组从后往前依次取最大的两个放入一组，
            // 而中间的，就是从i= 3*n-2开始，依次递减2，就是每次的中间最大值。
            for (int i = 3*n -2; i >= n; i-=2) {
                sum+=arr[i];
            }
            System.out.println(sum);

        }
    }
}
编辑于 2023-03-26 18:58:49 回复(0)
李逢溪头像 李逢溪 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    int n = 0;
    cin>>n;
    vector<int> v;
    v.resize(n*3);
    for(auto& e : v)
    {
        cin>>e;
    }
    sort(v.begin(), v.end());
    long long sum = 0;
    int j = v.size() - 2;
    for(int i = 0; i < n; i++)
    {
        sum += v[j];
        j -= 2;
    }
    cout<<sum<<endl;
    return 0;
}

发表于 2023-03-12 16:29:23 回复(0)
牛客64606183号头像 牛客64606183号
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int[]array=new int[3*n];
        for(int i=0;i<3*n;i++){
            array[i]=in.nextInt();
        }
        long count=0;
        Arrays.sort(array);
        for(int i=n;i<3*n;i+=+2){
            count+=array[i];
        }
        System.out.println(count);
    }
}
发表于 2022-12-11 15:25:30 回复(0)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 c#工程师 数据库工程师 排序 信息技术岗 贪心 区块链 测试开发工程师 2020 大数据开发工程师 数据分析师 Java工程师 牛客
来自：【2017】牛客模考（...
难度：
70条回答 26448浏览

热门推荐

通过挑战的用户

相关试题

组队竞赛

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号