Menu Sidebar
Menu

meet in middle

[SPOJ] PALIN – The Next Palindrome

原题: http://www.spoj.com/problems/PALIN/ 题目大意: 给任意一个数, 找到比这个数大的最小的一个回文数字. 分析: 这题要考虑的情况很多, 比如例子中的808, 我们需要把0改成1, 因为如果我们改动最后的8, 前边的8也要增加, 所以改变的总量会更大, 只能改变0. 所以第一条就是, 我们要从数字的中间改. 另一个是2133变成2222. 这个改变的过程是2133->2132->2112->2222, 这里, 我们用的是meet in mid的策略, 我们要比较前边和后边的数字, 如果他们是一样的, 那么就忽略, 如果他们不一样, 前边比后边大, 就把后边改成前边的, 这样相当于增加了,所以就结束了. 如果后边大, 把前边赋值后边, 但是继续程序.最后一种情况是, 99999->100001. 我们把所有的9变成0, 然后最后的9变成1,然后前边加1. public void solve(int testNumber, InputReader in, OutputWriter out) { int t = in.readInt(); for (int i = 0; i < t; i++) […]

Find the point in array with equal sum of left and right. 找数组中的一个点, 使左右的合相等

给一个数组, 找数组中的一个点, 使在这点的左边数的和,等于右边的和. 注意: 这里不是sorted数组. 所以我们用meet in middle的做法. 而且数组会有负数, 对于负数, 我们需要在另一边加上这个数. public int find (int[] nums) { int l = 0; int r = nums.length – 1; int suml = 0; // sum of left side int sumr = 0; // sun of right side while (l <= r) { if (l == r && […]

[SPOJ] NOTATRI – Not a Triangle

原题:http://www.spoj.com/problems/NOTATRI/ 题目大意:给一个数组, 找到其中不能组成三角形的3-tuple的个数. 分析:睡前A一道. 简单的计算. 两边之和<第三边, 先排序一下数组, 然后把第三边取数组最后一个, 也是最大一个数. 然后两个指针left和right, meet in middle, 个数是 right-left, 因为每次当满足条件时, 所有在right和left中的元素, 都可以看成以当前i为第三边和当前的left为一条边时, 移动right往left靠拢,这些可能的组合, 都是满足条件的, 因为right靠谱left是一个递减的过程. public void solve(int testNumber, InputReader in, OutputWriter out) { int t = in.readInt(); while (t != 0){ int[] nums = IOUtils.readIntArray(in,t); out.printLine(solve(nums)); t = in.readInt(); } } private int solve(int[] nums){ int res = […]

书脊

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

February 2023
M T W T F S S
 12345
6789101112
13141516171819
20212223242526
2728