好久没有写解题报告了。昨晚11点打了一场cf,感觉一般般。

题意:给定两个序列,可以任意交换两个序列的两次元素,最多交换两次,问两个序列的差值的绝对值最小是多少。

思路:最多交换两次嘛。那么交换0/1次的就比较简单了,直接nm的复杂度扫一遍就可以了。

难就难在这个交换两次的地方如何处理。比赛的时候,思路虽然和题解差不多,但是我的思路的那种处理方法没有办法防止交换的不是同一个元素。

题解的方法就比较巧妙了,直接预处理一下a序列的元素的任意两个的组合情况,b序列的任意两个的组合情况。

我们可以根据b序列的组合情况来去查找a序列的组合情况。比如 suma – sumb 差值为10,如果在b序列里面有一个组合值为1,那么我们需要从a序列里面找一个值为6的(这一块自己写一写就可以发现怎么得来的)。

在去寻找a序列的值的时候,用二分查一下就可以了。用map比较方便。

 

 

HDU 4768 Flyer(二分答案)

题意:给定n个表达式, 求出所有的y值,y = a[i] + c[i]*k <= b[i] (k >=0),问所有的y值中奇数个数的数值。并求出个数,题目制定所有的y中最多有一个奇...

阅读全文

UVA 1471 – Defense Lines(高效算法/LIS)

题意:给定个数为n且都是正数的序列,删除其中的一段连续序列,求得到的新的序列的最长连续序列的长度。   思路:求出每个位置以此位置为左端点的上升序...

阅读全文

Codeforces Round #299 (Div. 1)A. Tavas and Karafs(二分答案)

题意:给定一个等差序列(递增),给一个 左边界l(第l项),你每次都可以选 l  ~r中的 m 个数,一天使得这m个数都减一,求t天可以把 l~r的数字都变成0的最大...

阅读全文

欢迎留言

*