视频: https://youtu.be/nPL8eD4K-Hw
视频: https://youtu.be/x95uzweZPUk
视频: https://youtu.be/w7STY9FjJWU
视频: https://youtu.be/sbjVyhEJyEI
视频: https://www.youtube.com/watch?v=SnULWIsf9l4
网前勾对角: 同侧半区, 教练出小球, 学员勾对角.
现在已经很注意举拍的, 下次可以再举高点, 以前发力全是大臂力量, 所以不够集中, 通过提高举拍质量, 现在已经能感受到小臂发力了.
视频地址: https://youtu.be/CMtX5rXx718
高吊放网: 同侧半区, 教练出高远球, 学员吊网前, 学员放同侧小球, 教练跳球.
杀球上网: 同侧半区, 教练出高远球, 学员从中间后撤杀球, 应杀同侧区域, 教练回小球, 学员上网.
杀球反手抽底: 同侧半区, 教练出高远球, 学员从中间后撤杀球, 应杀同侧区域, 教练回斜线小球, 学员跟上反手抽底线.
高吊放网: 同侧半区, 教练出高远球, 学员吊网前, 学员放同侧小球, 教练跳球.
链接: https://codeforces.com/contest/609/problem/D
|
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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
public class TaskD { public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); // numbers of days int m = in.readInt(); // total number of gadgets int k = in.readInt(); // required number of gadgets long s = in.readLong(); // number of $ int[] dollar = in.readIntArray(n); int[] pound = in.readIntArray(n); Pair<Integer, Integer>[] res = new Pair[k]; Item[] items = new Item[m]; for (int i = 0; i < m; i++) { items[i] = new Item(); items[i].type = in.readInt(); items[i].cost = in.readInt(); items[i].pos = i; } int start = 0; int end = n-1; int minDay = -1; while (end >= start) { int mid = start + (end -start) / 2; if (canDo(mid, dollar, m, k, s, pound, items, res)) { minDay = mid; end = mid - 1; } else { start = mid +1; } } if (minDay == -1) { out.printLine("-1"); } else { out.printLine(minDay+1); for (int i = 0; i < k; i++) { out.printLine((res[i].first+1)+" "+(res[i].second+1)); } } } private boolean canDo(int cur, int[] dollar, int m, int k, long s, int[] pound, Item[] items,Pair<Integer, Integer>[] res) { int dayD = -1; int dayP = -1; int minD = Integer.MAX_VALUE; int minP = Integer.MAX_VALUE; for (int i = 0; i <= cur; i++) { if (dollar[i] < minD) { minD = dollar[i]; dayD = i; } if (pound[i] < minP) { minP = pound[i]; dayP = i; } } for (int i = 0; i < m; i++) { if (items[i].type == 1){ items[i].need = BigDecimal.valueOf(minD).multiply(BigDecimal.valueOf(items[i].cost)); } else { items[i].need = BigDecimal.valueOf(minP).multiply(BigDecimal.valueOf(items[i].cost)); } } Arrays.sort(items); // sort by the required burles BigDecimal sum = new BigDecimal(0); for (int i = 0; i < k; i++) { sum = sum.add(items[i].need); } if (sum.compareTo(new BigDecimal(s)) <= 0) { for (int i = 0; i < k; i++) { if (items[i].type == 1) { res[i] = Pair.makePair(items[i].pos,dayD); } else { res[i] = Pair.makePair(items[i].pos,dayP); } } return true; } else { return false; } } class Item implements Comparable<Item> { int type; int cost; int pos; BigDecimal need; @Override public int compareTo(Item o) { return need.compareTo(o.need); } } } |
这题好tricky, 好几个test都是c++的ll类型的, java做着好头疼.
首先根据题意可以看出来, 能在x天完成任务(从m中买到k个item), 在剩下的x+1天也能完成, 所以具有单调性, 可以在排序(根据买东西的实际价格排序, 这里的实际价格是第i天的汇率*单价).
其次我们的目标是买k个东西, 那么如果给定某天x, 如何用同样的钱(假设), 买更多的东西?, 肯定是先买便宜的啊. 所以是贪心算法. 既然是贪心算法, 我们就要找到算法的关键, 那就是如何在m天中的第i天买到更便宜的东西? 显然, 我们知道汇率和单价是乘法关系, 就要分别找到前i天的两种货币的最低汇率minD和minP, 然后我们要测试一下在cur天的时候, 我们能否买够所需的k个物品. 这里我们用minD和minP分别乘以m个物品, 然后得到的价格就是cur天实际价格, 然后通过排序并且提取前k个物品, 我们就可以测试能否在cur天购买到k个物品.
链接: https://codeforces.com/contest/609/problem/C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class TaskC { public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] ary = in.readIntArray(n); long res = 0; Arrays.sort(ary); int sum = 0; for (int i:ary) { sum+=i; } for (int i = 0; i < n/2; i++) { int b = sum / (n - i); res += Math.abs(ary[i] - b); sum -= b; } out.print(res); } } |
公式推导题, 先要排序ary, 然后算出数组的和sum. 然后可以观察到, 我们可以把相对大的数给相对小的数以便于达到平衡, 这种平衡有两个可能性, 一种是两数合为奇数, 比如数组 1 2 4, 4+1=5, 5是奇数, 这种情况下给完后的差是1, 即2 2 3, 3-2=1. 另外一种情况是两数合为偶数, 比如 1 2 3, 3+1=4, 4是偶数. 这种情况下给完后的差是0, 即2 2 2, 2-2=0. 所以可以证明这种先排序后两端互相给的方法, 是答案要的方法, 即miimize(Ma – Mb), where a is the most loaded server and b is the least loaded one.
最后我们需要找到平衡数组b, 通过观察我们知道, 我们只需要遍历一半的数组就可以得到答案, 因为我们是通过”给数”的方法, 所以我们用一个循环遍历一半的数组. 通过再次观察不难发现, 比如数组 1 2 3 4 的平衡数组是2 2 3 3 (4给1 1次). 这个平衡数组的sum是1+2+3+4 = 10. 如果我们把10均分, 那么久变成10/4 = 2, 10 mod 4 = 2, 这里的意思是平衡数组中绝大部分是10/4 = 2, 其中有10 mod 4个数比其他数多1. 再举例, 1 2 3 4 5, sum = 15. 15/5 = 3, 15 mod 5 = 0 (整除). 这里说明它的平衡数组是 3 3 3 3 3, 有0个(没有)数比其他数多1. 现在我们验证一下, 5给1 两次, 数组变成 3 2 3 4 3, 4 给2 一次变成3 3 3 3 3. 结束
上面的code并不是这个答案的code. 上面的code用了一个更好的数学方法. 通过上面的观察可以看出, ary的数字a是由两部分组成, 一个数组的均值(sum/n)+多的1(如果有). 这个题问的是第二部分数字的合, 我们现在已知前边两个部分 那么只需要用数字ary[i] – 当前数组的均值sum/n, 即Math.abs(ary[i] – b), 然后不要忘了计算下一个数字均值的时候, 应该减去当前的均值.