# 挑战程序竞赛系列（23）：3.2折半枚举

## POJ 2785: 4 Values whose Sum is 0

    void solve() {
int n = ni();
int[] A = new int[n];
int[] B = new int[n];
int[] C = new int[n];
int[] D = new int[n];
for (int i = 0; i < n; ++i){
A[i] = ni();
B[i] = ni();
C[i] = ni();
D[i] = ni();
}

int[] arra = new int[n * n];
for (int i = 0, k = 0; i < n; ++i){
for (int j = 0; j < n; ++j){
arra[k++] = C[i] + D[j];
}
}
Arrays.sort(arra);

long cnt = 0;
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j){
int key = -(A[i] + B[j]);
int lo = lowBound(arra, key);
int hi = upBound(arra, key);
if (lo == -1 || hi == -1) continue;
cnt += (hi - lo + 1);
}
}
out.println(cnt);
}

private int lowBound(int[] arra, int key){
int lf = 0, rt = arra.length - 1;
while (lf < rt){
int mid = lf + (rt - lf) / 2;
if (arra[mid] < key) lf = mid + 1;
else rt = mid;
}
if (arra[rt] == key) return rt;
return -1;
}

private int upBound(int[] arra, int key){
int lf = 0, rt = arra.length - 1;
while (lf < rt){
int mid = lf + (rt - lf + 1) / 2;
if (arra[mid] > key) rt = mid - 1;
else lf = mid;
}
if (arra[lf] == key) return lf;
return -1;
}

## POJ 3977: Subsets

• 用二分法逼近答案，因为可能会有多解的情况
• 所以需要进行两次，第一次寻找最接近0的负值，第二次寻找最接近0的正值。
• 然后扫描这两者之间的所有元素，找出sum最小，且count最小的组合

    public static void main(String[] args) throws NumberFormatException, IOException {
while (true) {
if (n == 0) break;
long[] arra = new long[n];

for (int i = 0; i < n; i++) {
arra[i] = new Long(input[i]);
}

long[] LL = new long[n];
long[] RR = new long[n];
int LN = 0, RN = 0;

for (int i = 0; i < n; i += 2) {
LL[LN++] = arra[i];
if (i + 1 < n)
RR[RN++] = arra[i + 1];
}

if (RN == 0) {
System.out.println(LL[0] + " " + 1);
continue;
}

Sum[] sums = new Sum[1 << RN];
for (int i = 0; i < 1 << RN; ++i) {
long sum = 0;
int cnt = 0;
for (int j = 0; j < RN; ++j) {
if ((i & (1 << j)) != 0) {
sum += RR[j];
cnt++;
}
}
sums[i] = new Sum(sum, cnt);
}
Arrays.sort(sums);

long ans = 1000000000000001l;
int ansc = 36;
for (int i = 0; i < 1 << LN; ++i) {
long key = 0;
int cnt = 0;
for (int j = 0; j < LN; ++j) {
if ((i & (1 << j)) != 0) {
key += LL[j];
cnt++;
}
}

int l = 0;
int r = sums.length;
while (r - l > 1) {
int m = (l + r) / 2;
if (sums[m].sum + key >= 0) {
r = m;
} else {
l = m;
}
}
int L = l;
l = -1;
r = sums.length - 1;
while (r - l > 1) {
int m = (l + r) / 2;
if (sums[m].sum + key > 0) {
r = m;
} else {
l = m;
}
}
int R = r;
for(int k = L; k <= R; ++k){
long tempsum = Math.abs(sums[k].sum + key);
int tempcount = sums[k].cnt + cnt;
if (tempcount == 0) continue;

if(tempsum < ans){
ans = tempsum;
ansc = tempcount;
}
else if(tempsum == ans & tempcount < ansc){
ansc = tempcount;
}
}
}
System.out.println(ans + " " + ansc);
}
}

WA到心碎，正确代码可以参考http://poj.org/showmessage?message_id=346495

## POJ 2549: Sumsets

    void solve() {
while (true){
int n = ni();
if (n == 0) break;
long[] arra = new long[n];
Map<Long, Integer> map = new HashMap<Long, Integer>();
for (int i = 0; i < n; ++i){
arra[i] = nl();
if (!map.containsKey(arra[i])){
map.put(arra[i], 0);
}
map.put(arra[i], map.get(arra[i]) + 1);
}

TwoSum[] sums = new TwoSum[n * n];
for (int i = 0; i < sums.length; ++i){
sums[i] = new TwoSum(Long.MAX_VALUE, -1, -1);
}

int N = 0;
for (int i = 0; i < n; ++i){
if (map.get(arra[i]) != 1) continue;
for (int j = 0; j < n; ++j){
if (i == j) continue;
sums[N++] = new TwoSum(arra[i] - arra[j], i, j);
}
}
Arrays.sort(sums);
long max = Long.MIN_VALUE;

for (int i = 0; i < n; ++i){
for (int j = i + 1; j < n; ++j){
long key = arra[i] + arra[j];
int lo = loBound(sums, N, key);
int hi = upBound(sums, N, key);
if (lo == -1 || hi == -1) continue;
for (int l = lo; l <= hi; ++l){
TwoSum sum = sums[l];
if (sum.i == i || sum.j == i || sum.i ==j || sum.j == j) continue;
max = Math.max(arra[sum.i], max);
}
}
}

if (max == Long.MIN_VALUE) out.println("no solution");
else out.println(max);

}
}

public int upBound(TwoSum[] sums, int len, long key){
int lf = 0, rt = len - 1;
while (lf < rt){
int mid = lf + (rt - lf + 1) / 2;
if (sums[mid].sum > key) rt = mid - 1;
else lf = mid;
}
if (sums[lf].sum == key) return lf;
return -1;
}

public int loBound(TwoSum[] sums, int len, long key){
int lf = 0, rt = len - 1;
while (lf < rt){
int mid = lf + (rt - lf) / 2;
if (sums[mid].sum < key) lf = mid + 1;
else rt = mid;
}
if (sums[rt].sum == key) return rt;
return -1;
}

class TwoSum implements Comparable<TwoSum>{
long sum;
int i;
int j;

public TwoSum(long sum, int i, int j) {
this.sum = sum;
this.i = i;
this.j = j;
}

@Override
public String toString() {
return "" + sum;
}

@Override
public int compareTo(TwoSum o) {
return this.sum < o.sum ? -1 : 1;
}
}

0 条评论

• ### K-th Smallest Prime Fraction

思路1： 一种聪明的做法，如果A = [1, 7, 23, 29, 47]，那么有：

• ### 挑战程序竞赛系列（36）：3.3线段树和平方分割

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（32）：4.5 A*与IDA*

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### LeetCode 323. 无向图中连通分量的数目（并查集）

给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。

• ### 2017.5.20欢(bei)乐(ju)赛解题报告

预计分数：100+20+50=first 实际分数：20+0+10=gg 水灾（sliker.cpp/c/pas） 1000MS  64MB 大雨应经下了几天雨...

• ### BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

Description 一个无向连通图，顶点从1编号到N，边从1编号到M。  小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当...

• ### OpenCV图像处理专栏十 | 利用中值滤波进行去雾

这是OpenCV图像处理专栏的第十篇文章，介绍一种利用中值滤波来实现去雾的算法。这个方法发表于国内的一篇论文，链接我放附录了。

• ### 1077: 输入入门(2)

描述:计算A+B 输入:输入第1行为一个整数n(1≤n≤10)，代表测试的组数。下面有n组测试数据，每组1行，为2个整数，为A, B。 输出:输出A+B的值...

• ### 排序算法——一篇文章搞懂常用的排序算法

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记...