Menu Sidebar
Menu

sorting

Maximum Gap

 

Codeforces Round #317 [AimFund Thanks-Round] (Div. 2) B. Order Book

原题: http://codeforces.com/contest/572/problem/B 题目大意: 对n个股票操作进行排序, 最后生成一个Order Book. 操作有两种, buy 和 sell, 后边是股票标号和价钱. 要求对相同操作的相同股票进行合并操作. 然后输出排序后前s个sell和buy的股票. 这里的排序要求是, 对于sell, 先对编号递增排序, 然后取前s (没有s个取所有). 然后再对编号递减排序. 对于buy直接递减排序即可. 分析: 用Java的TreeMap一下就出来了. 因为TreeMap本身就是有序的, 用Collections.reverseOrder()可以改变顺序. 然后取前s个的时候, 可以把set变成stream, 然后limit一下就可以

Codeforces Round #317 [AimFund Thanks-Round] (Div. 2) A. Arrays

原题: http://codeforces.com/contest/572/problem/A 题目大意: 给两个数组, 问是否能在第一个数组找到k个数,在第二个数组找到m个数, 使得所有在第一个数组找到的数小于第二个数组找到的数. 数组已排序. 分析: 因为数组已经排序, 所以如果在第一个数组前k个数字小于第二个数组后m个数字, 那么打印YES.如果不是, 打印NO

[LintCode] Merge Intervals

[LintCode] 3 Sum

[LintCode] 3 Sum Closest

[SPOJ] SBANK – Sorting Bank Accounts

原题: http://www.spoj.com/problems/SBANK/ 题目大意:  给n个银行交易帐号信息, 要求排序, 并且统计出现次数, 输出要有序,并且输出次数. 分析: 其实就是设计一个数据结构, 是Key-Value的, 并且有序. Key-Value就是Map了, 有序 自然就是TreeMap.

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:

最后看了一下答案, 发现是用两个set保存当前数字为等比中项的前后序列, 然后记录一下相同项的个数. 第二次扫描的时候, 如果当前数字能整除公比, 那么找到j,i,k的个数,相乘就是答案. 这里注意要用long存. 难怪我test老挂 答案code:

 

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

原题: http://codeforces.com/contest/567/problem/A 题目大意: 给一个数组, n个数, 有正有负, 已经排序好了, 让你输出每个数和数组中其他数的最大差和最小差. 分析: 已经排好, 所以遍历一遍,最小就是比较当前数字的左边或右边的差的绝对值, 最大就是比较当前数字和数组的头和数组的尾的差的绝对值, 就可以了, 注意第一个数和最后一个数没有左边或者右边.

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就行了.

Older Posts

书脊

倾城与倾国, 佳人难再得