poj 2785 折半枚举（与poj2549的区别）

本文主要是介绍poj 2785 折半枚举（与poj2549的区别），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

poj2549是纯粹的K*sum问题。

代码链接：http://blog.csdn.net/u012915516/article/details/24047761

poj2785看上去也想是k*sum问题。

但是当我入手的时候，完全就是O（N^4）。无法达到要求。

也就是说K*sum问题只限于一个数组。

而折半枚举可以在多个数数组也可以在一个数组身上作用。

在一个数组上作用的题目：poj3977

poj2785代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a[4010],b[4010],c[4010],d[4010],sum[4010*4010];
int main()
{ll n,ans=0;cin>>n;for(int i=0;i<n;i++)scanf("%lld %lld %lld %lld",&a[i],&b[i],&c[i],&d[i]);for(int i=0;i<n;i++)for(int j=0;j<n;j++)sum[i*n+j]=c[i]+d[j];sort(sum,sum+n*n);for(int i=0;i<n;i++)for(int j=0;j<n;j++)ans+=upper_bound(sum,sum+n*n,-a[i]-b[j])-lower_bound(sum,sum+n*n,-a[i]-b[j]);printf("%lld\n",ans);return 0;
}

这篇关于poj 2785 折半枚举（与poj2549的区别）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---