初始有两个长度均为 的数组 和 .
牛牛想在其中选出 个数求和,选数的规则如下:
1. 每个 数组中的数只能被选择一次,而每个 数组中的数可以被选择无数次。
2. 想要选择 数组中的数,就必须先选择 数组中相同下标的数。例如:想要选择 ,就必须先选择 .
在上述规则下,最终选出的 个数求和的最大值是多少?
第一行输入一个正整数 ,代表测试数据组数。
对于每组测试数据,第一行输入两个正整数 ,依次代表需要找 个数求和以及 数组的长度。
接下去 行,每行两个正整数 .
对于每组测试数据,一行输出一个正整数代表答案。
1 6 3 6 0 1 6 4 3
31
选择 以及四次 ,可以达到 ,同时,其它选数方案求得的和,一定不会超过 .
import java.util.*; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int group = sc.nextInt(); for (int i = 0; i < group; i++) { int n = sc.nextInt(); int m = sc.nextInt(); int[][] array = new int[m][2]; int[] a = new int[m]; for (int j = 0; j < m; j++) { array[j][0] = sc.nextInt(); array[j][1] = sc.nextInt(); } Arrays.sort(array, ((o1, o2) -> o2[0] - o1[0])); for (int j = 0; j < m; j++) { if (j == 0) { a[j] = array[j][0]; } else { a[j] = a[j - 1] + array[j][0]; } } int max = 0; for (int j = 0; j < m; j++) { int curB = array[j][1]; int count = n; int curVal = 0; int left = 0; int right = m - 1; // 大于等于 curB 有 left 个 while (left <= right) { int mid = left + (right - left) / 2; if (array[mid][0] >= curB) { left = mid + 1; } else { right = mid - 1; } } if (left >= count) { max = Math.max(max, a[count - 1]); continue; } else { if (left != 0) { curVal += a[left - 1]; count -= left; } if (j < left) { curVal += count * curB; } else { curVal = curVal + array[j][0] + (count - 1) * curB; } } max = Math.max(max, curVal); } System.out.println(max); } } }