Menu Sidebar
Menu

sorting

Codeforces Round #Pi (Div. 2) C. Geometric Progression

原题: http://codeforces.com/contest/567/problem/C 题目大意: 给一个n大小数组, 问其中的子序列(非连续)能组成多少个已p为公比的等比序列, 且长度为3. 分析: 这题卡了好久, 我用找等差数列的方法改的. 后来总是过不了test. 可是怎么看我的是O(nlgn)的复杂度, 所以过不了大的test case 肯定是有O(n)的. 于是开始想啊想啊….最后想到了是用等比中项的性质. 首先上一个过不了的code: public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int p = in.readInt(); IntPair[] nums = new IntPair[n]; for (int i = 0; i < nums.length; i++) { nums[i] = new IntPair(in.readInt(),i); } Arrays.sort(nums); int count […]

Codeforces Round #Pi (Div. 2) A. Lineland Mail

原题: http://codeforces.com/contest/567/problem/A 题目大意: 给一个数组, n个数, 有正有负, 已经排序好了, 让你输出每个数和数组中其他数的最大差和最小差. 分析: 已经排好, 所以遍历一遍,最小就是比较当前数字的左边或右边的差的绝对值, 最大就是比较当前数字和数组的头和数组的尾的差的绝对值, 就可以了, 注意第一个数和最后一个数没有左边或者右边. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] ary = IOUtils.readIntArray(in, n); out.printLine(Math.abs(ary[1] – ary[0]) + ” ” + Math.abs(ary[0] – ary[ary.length – 1])); for (int i = 1; i < ary.length-1; i++) { out.printLine(Math.min(Math.abs(ary[i] – […]

Codeforces Round #307 (Div. 2) A. GukiZ and Contest

原题: http://codeforces.com/contest/551/problem/A 题目大意: 给n个人, 每个人都有rank, rank最高的人是1, 同一个rank的人得分一样, 不同rank的人,得分是前边rank人数的合, 问返回的数组是什么. 分析: 我看题目是sorting, 我没sort唉. 一共rank才2000, 用个count数组记录一下, 然后从后往前(从大rank到小rank)扫数组,每次扫都取合传给下一个rank. 然后再走一般数组打印出来对应的rank就行了. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] count = new int[2005]; int[] nums = new int[n]; for (int i = 0; i < n; i++) { int t = in.readInt(); count[t]++; nums[i] = […]

Codeforces Round #313 (Div. 2) D. Equivalent Strings

原题:http://codeforces.com/contest/560/problem/D 题目大意: 给字符串a和b, 定义a和b是等价的,如果: a和b相等. a等分成a1,a2,b等分成b1,b2, (a1==b1 && a2==b2) || (a2==b1 && a1==b2) 分析: 就暴呗…我也不知道为什么我暴就报错, 是因为java的原因么, 我看人家同样码用c++, 都飞快的. public void solve(int testNumber, InputReader in, OutputWriter out) { String a = in.readString(); String b = in.readString(); if (solve(a,b)) out.print(“YES”); else out.print(“NO”); } private boolean solve(String a, String b) { if (a.length() % 2 != 0 || […]

Codeforces Round #312 (Div. 2) A. Lala Land and Apple Trees

原题:http://codeforces.com/problemset/problem/558/A 题目大意: 坐标轴上, 每个坐标上有一颗苹果树, 坐标的值代表的值是苹果的数量, 人从0开始走, 可以往左,也可以往右, 当遇到一个苹果树时, 人必须往反向走, 问:最多拿多少个的苹果? 分析: 无非开始往左or往右, 两种情况, 当遇到另一边没有树的时候, 停止, 所以最多拿max([left+1,right],[right+1,left]).left,right 原点左右的树的数量. 建个Pair<Integer,Integer>, 前边是index, 后边是value, 然后sort下 加一下就出来了. public void solve(int testNumber, Scanner in, PrintWriter out) { int n = in.nextInt(); ArrayList<Pair<Integer,Integer>> pos = new ArrayList<Pair<Integer,Integer>>(); ArrayList<Pair<Integer,Integer>> neg = new ArrayList<Pair<Integer, Integer>>(); for (int i = 0; i < n; i++) […]

Newer Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

April 2024
M T W T F S S
1234567
891011121314
15161718192021
22232425262728
2930  
© 2024 书脊 | 这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.