Educational Codeforces Round 110 (Rated for Div. 2)B. Array Reodering
给一个数组, 可以reorder这个数组, 求最大数量的pair, 使得gcd(ary[i], ary[j] * 2) >1 where i < j.
这个题就是需要思考, 我暴力的求解了一下, 发现过不了. 这题求一个数和2个倍数的gcd的大于1(非互质)个数. 因为能无限制reorder, 所以主要看这个数是不是2的倍数, 即是否可以被2整除, 如果可以, 假如ary[i] = 4, 那么肯定和 ary[j] * 2的gcd>1, 无论ary[j]是多少.
所以把数字分成两类, 一类是2的倍数, 另一类是非2的倍数, 然后排序下, 找一边即可.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
package readman; import net.egork.generated.collections.*; import net.egork.generated.collections.list.IntArrayList; import net.egork.io.InputReader; import net.egork.io.OutputWriter; import java.util.*; import static net.egork.numbers.IntegerUtils.gcd; public class TaskB { public void solve(int testNumber, InputReader in, OutputWriter out) { int k = in.readInt(); for (int i = 0; i < k; i++) { int f = in.readInt(); out.printLine(solve(in.readIntArray(f))); } } private int solve(int[] arr) { int count = 0; List<Integer> l1 = new ArrayList<>(); List<Integer> l2 = new ArrayList<>(); for(int a : arr){ if(a % 2 == 0) l2.add(a); else l1.add(a); } Collections.sort(l1, Collections.reverseOrder()); Collections.sort(l2, Collections.reverseOrder()); List<Integer> list = new ArrayList<>(); list.addAll(l2); list.addAll(l1); for (int i = 0; i < list.size(); i++) { for (int j = i + 1; j < list.size(); j++) { if (gcd(list.get(i), list.get(j) * 2) > 1) count++; } } return count; } } |