输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)
第二行包括3*n个整数a_i(1 ≤ a_i ≤ 10^9),表示每个参赛选手的水平值.
输出一个整数表示所有队伍的水平值总和最大值.
2 5 2 8 5 1 5
10
//最小和最大次大组队,次小和第三大第四大组队…… //如,123456789 //下标012345678 //组队方案如下: //189,267,345 水平值总和为8+6+4=18,是最大值 //每队队员中第二高水平值的下标:size-2*i(i=1,2,...,n) //所有队伍的水平值总和=每队队员中第二高水平值的总和 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n = 0;//声明n,表示组数 while (cin >> n)//输入n { vector<int> a;//存放每个选手的水平值 a.resize(3 * n);//扩容 for (int i = 0; i < 3 * n; ++i) { cin >> a[i];//输入每个选手的水平值 } sort(a.begin(), a.end());//给选手的水平值排序 long long sum = 0;//声明sum,表示总和,值可能很大,用long long类型 for (int i = 1; i <= n; ++i) { sum += a[a.size() - 2 * i];//sum累加 } cout << sum << endl;//输出sum } return 0; }
#include<vector> (721)#include<iostream> #include<algorithm> using namespace std; int main() { long long res=0,n; long long temp; cin>>n; int a = 3*n; vector<long long> ve; while(a-- > 0) { cin>>temp; ve.push_back(temp); } sort(ve.begin(),ve.begin()+3*n,greater<int>()); for(int i=1;i<=(2*n-1);i=i+2) res = res + ve[i]; cout<<res; }
#include <iostream> #include<algorithm> using namespace std; const int M=300003; int n; int a[M]; int main() { cin>>n; for(int i=0;i<3*n;i++) cin>>a[i]; sort(a,a+3*n); long long ans=0; for(int i=3*n-2;i>=n;i-=2) ans+=a[i]; cout<<ans<<endl; return 0; } // 64 位输出请用 printf(\"%lld\")题目比较简单,不要想复杂就好
分析:将所有数存入arr数组中,先将数组进行排序(从小到大),每次都取数组中最小的一个、最大的一个和次大的一个,这样可以保证每次分组中拿到最大的可能的数
import java.util.Arrays; import java.util.Scanner; public class demo1 { //组队竞赛 public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] arr = new int[3 * n]; for(int i = 0; i < 3 * n; i++) { arr[i] = in.nextInt(); } Arrays.sort(arr); // sum 的值可能会很大,所以用 Long 类型 long sum = 0; for(int i = 0; i < n; i++) { sum += arr[arr.length - 2 * (i + 1)]; } System.out.println(sum); } }
分析:将所有数存入arr数组中,竞赛时分组要使得所有组的中位数之和最大,可以先将数组进行排序(从小到大)
每次都取数组中最小的一个、最大的一个和次大的一个,这样可以保证每次分组中拿到最大的可能的数
如:1 2 3 4 5 6 7 8 9
分组:189 267 345
则中位数最大和为 8+6+4=18
计算这几个数的下标公式:arr.length() - 2 * (i + 1)
import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); //输入组数 int n = sc.nextInt(); //存储所有数据的数组 int[] arr = new int[3 * n]; //输入所有队员的水平值 for(int i = 0; i < 3 * n; i++) { arr[i] = sc.nextInt(); } //将数组进行排序 Arrays.sort(arr); //存储最大水平和 long sum = 0; //后 2/3 个数字的奇数位的和 //根据公式计算最大水平和 for(int i = 0; i < n; i++) { sum += arr[3 * n - 2 * (i + 1)]; } //输出结果 System.out.println(sum); } }
还有一种解法就是我没发现取的数就是排序后数组中后 2/3 的数据中从最小的一个开始依次跳一个的所有数之和
即:后 2/3 个数中所有位置为奇数的数
如:1 2 3 4 5 6 7 8 9
456789中:4+6+8=18
import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); //输入组数 int n = sc.nextInt(); //存储所有数据的数组 int[] arr = new int[3 * n]; //输入所有队员的水平值 for(int i = 0; i < 3 * n; i++) { arr[i] = sc.nextInt(); } //将数组进行排序 Arrays.sort(arr); //存储最大水平和 long sum = 0; //后 2/3 个数字的奇数位的和 for (int i = n; i < 3 * n; i += 2) { sum += arr[i]; } //输出结果 System.out.println(sum); } }
public class Main1 { //保证每组的第二个值取到能选择的最大值就可以, // 我们每次尽量取最大,但是最大的数不可能是中位数, // 所以退而求其次,取每组中第二大的 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); long[] array = new long[3 * n]; for (int i = 0; i < (3 * n); i++) { array[i] = scanner.nextLong(); } Arrays.sort(array); long sum = 0; for (int i = 0; i < n; i++) { sum += array[array.length - (2 * (i + 1))]; } System.out.println(sum); } } }
#include<iostream> #include<vector> #include <algorithm> using namespace std; int main() { vector<int> v; long long nums; cin >> nums; v.reserve(3 * nums); for (size_t i = 0; i < 3 * nums; ++i) { int t; cin >> t; v.push_back(t); } sort(v.begin(), v.end());//排序 long long tmp = 0, j = 0; for (int i = (3 * nums) - 2; i >= 0; i -= 2) //1 2 5 5 7 8,每次取 7 5 即可 { if (j < nums) { tmp += v[i]; ++j; } else break; } cout << tmp << endl; return 0; }
既然不能选最大,我们就选第二大,将数组排个序,然后获取下标为 n, n+2, n+4,...,3n-2 的元素并求和好了
这样就获取到所有队伍的水平值总和最大值.也可以这么理解
我们看测试用例
5 2 8 5 1 5
我们将其排序
1 2 5 5 5 8
不妨令 1 5 5 为一个组合
2 5 8 作为另一个组合
为什么要这么划分呢?
既然队伍的平均水平是队伍里第二水平的和
这样的话,我们让队伍的最小的元素就取排序后数组中的前n-1(数组下标从0开始)个元素好了
接下来的问题就是剩下的2n个元素怎么划分的问题了,我们假设这样分:
从n-2n-1的作为队伍的第二,但是这样一来,我们得到的和一定不是最大值,我们这样考虑,假如,n和n+1一组,n+2和n+3一组,这样每组的第二分别是 n, n+2, n+4,...,3n-2,显然n+1 < n+2, n+2 < n+4, n+3 < n+6, 2n < 3n-2.
这就是我们要的最大的结果呀
#include <iostream> #include <string> #include <vector> #include <algorithm> #define DEBUG 0 int main(void) { std::vector<int> array(300003, 0); int n = 0; int i = 0; long long sum = 0; while((std::cin >> n) && ((n >= 1) && (n <= 100000))) { #if DEBUG std::cout << "[DEBUG] n = " << n << std::endl; #endif for(i = 0; i < 3*n; ++i) { std::cin >> array[i]; } #if DEBUG std::cout << "[DEBUG] before sort, array = "; for(i = 0; i < 3*n; ++i) { std::cout << array[i] << " "; } std::cout << std::endl; #endif std::sort(array.begin(), array.begin() + 3*n); #if DEBUG std::cout << "[DEBUG] after sort, array = "; for(i = 0; i < 3*n; ++i) { std::cout << array[i] << " "; } std::cout << std::endl; #endif for(i = n; i <= 3*n -2; i = i+2) { #if DEBUG std::cout << "[DEBUG] array[" << i << "] = " << array[i] << std::endl; #endif sum += array[i]; } std::cout << sum << std::endl; sum = 0; array.clear(); #if DEBUG std::cout << "[DEBUG] array.capacity() = " << array.capacity() << std::endl; #endif } return 0; }