poj 折半搜索

poj2549 Sumsets

题目链接： http://poj.org/problem?id=2549

题意：给你一个含有n(n<=1000)个数的数列，问这个数列中是否存在四个不同的数a,b,c,d,使a+b+c=d;若存在则输出最大的d

思路：完全暴力的话O(n^4)，会T，可以考虑双向搜索，公式变形为a+b=d-c；分别枚举a+b和c-d，将值和下标存在结构体中，再二分查找即可

#include
#include
#include
#include
#include
#include
using namespace std;
struct Z{
int s;
int x;
int y;
bool operator < (const Z& b)const

    {

        return s < b.s;

    }
}z[1000005],m[1000005];
int n,a[1005];
bool ok(Z& a, Z& b)

{
    return a.x != b.x && a.y != b.y && a.x != b.y && a.y != b.x;
}
int main(){
    while((cin>>n)&&n!=0){
    int ans=-536870912;
    for(int i=0;i>a[i];
    sort(a,a+n);
    int k=0;
    for(int i=0;i

poj3977 Subset
题目链接： http://poj.org/problem?id=3977
题意：给你一个含n(n<=35)个数的数组,让你在数组中选出一个非空子集，使其元素和的绝对值最小，输出子集元素的个数以及元素和的绝对值，若两个子集元素和相等，输出元素个数小的那个。
思路：如果直接暴力枚举，复杂度O(2^n)，n为35时会超时，故可以考虑折半枚举，利用二进制将和以及元素个数存在两个结构体数组中，先预判 两个结构体是否满足题意，再将其中一个元素和取相反数后排序，因为总元素和越接近零越好，再二分查找即可，用lower_bound时考虑查找到的下标和他前一个下标，比较元素和以及元素个数，不断更新即可

#include
#include
#include
#include
using namespace std;
struct Z{
	long long int x;
	int y;
	bool operator < (const Z& b)const
    {
        if(x!=b.x)
        return x < b.x;
        return y>n)&&n!=0){
        for(int i=0;i<300005;i++)
           a[i].x=a[i].y=b[i].x=b[i].y=0;
        long long int sum=1e17;
        int ans=40;
        for(int i=0;i>c[i];
        int n1=n/2;
        for(int i=0;i<1<>j&1&&(i!=0||j!=0)){
                    a[i-1].x+=c[j];
                    a[i-1].y++;
                }
            }

        }
        int n2=n-n1;
        for(int i=0;i<(1<>j&1&&(i!=0||j!=0)){
                    b[i-1].x+=c[j+n1];
                    b[i-1].y++;
                }
            }

        }
      for(int i=0;i<(1<0){
            	if(abs1(b[t-1].x-a[i].x)

poj2785 4 Values whose Sum is 0
题目链接: http://poj.org/problem?id=2785
挑战P160
题意：给你各有n个整数的四个数组，问从每个数列中取出一个数使四个数之和为0，问共有多少种取法，一个数列中有多个相同的数字时，将他们当成不同的数字看待，1<=n<=4000;
思路：完全暴力枚举O(n^4)肯定会超时，可以考虑拆成两半后枚举设四个数a+b+c+d=0，先将a+b所有组合存在一个数组中并排序O(n^2)，再枚举c+d（O(n^2)），对于每个c+d，在a+b的数列中二分搜索-(c+d)，总复杂度O(n^2*log n);
直接贴书上代码：

#include
#include
#include
using namespace std;
int a[4005],b[4005],c[4005],d[4005],cd[16000005];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i

ACM-POJ

poj 折半搜索

poj2549 Sumsets

poj3977 Subset

poj2785 4 Values whose Sum is 0

相关

标签