首页 > 代码库 > POJ 3977Subset(枚举+二分)
POJ 3977Subset(枚举+二分)
Subset
Time Limit: 30000MS | Memory Limit: 65536K | |
Total Submissions: 1562 | Accepted: 261 |
Description
Given a list of N integers with absolute values no larger than 1015, find a non empty subset of these numbers which minimizes the absolute value of the sum of its elements. In case there are multiple subsets, choose the one with fewer elements.
Input
The input contains multiple data sets, the first line of each data set contains N <= 35, the number of elements, the next line contains N numbers no larger than 1015 in absolute value and separated by a single space. The input is terminated with N = 0
Output
For each data set in the input print two integers, the minimum absolute sum and the number of elements in the optimal subset.
Sample Input
1 10 3 20 100 -100 0
Sample Output
10 1 0 2
Source
题目大意:让你从n个数里面找任意个数(>0),使他们的和最小,如果有多组和一样最小,输出最小和且最小个数。
解题思路:当时只想到了,2^35复杂度的枚举,当时想了二分,不过当时想的是分正数负数来构成组合。很久没做题,连想都不敢想了。。
把n个数,分成两半,前一半用来枚举,后一半用来二分,需要记录多少个构成的数字,如果有多种,选最小的即可。
开始想的是选0有点特殊,上午写的时候先处理前一半从一个开始枚举,不能取0个,然后再用后一半构造二分空间,此时不用考虑一个也不取,因为前面已经考虑了。
不知道啥原因,一直WA,一直WA。
就想把算法化简单一点,其实,前半部分后半部分都是0个的话,可以直接在循环中控制。。
A的不容易啊。。
题目地址:Subset
AC代码:
#include<cstdio> #include<iostream> #include<cstring> #include<queue> #include<algorithm> #include<cmath> #include<map> #define ll long long using namespace std; const int maxn=1000005; int n,m,p; ll a[35]; struct node { ll val; int len; } nod1[maxn],nod[maxn]; //map <ll,int> mq; //主要控制存在数里面存最小的 int erfen(ll x) { int l=0,r=p-1,mid; while(r>=l) { mid=(l+r)>>1; if(nod[mid].val>=x) r=mid-1; else l=mid+1; } return l; } int cmp(node p1,node p2) { if(p1.val<p2.val) return 1; if(p1.val==p2.val&&p1.len<p2.len) return 1; return 0; } int main() { int i; int x,s,res; ll ans; while(cin>>n&&n) { for(i=0; i<n; i++) cin>>a[i]; ans=1e15+5,res=50; m=n/2; //前面用来枚举,后面用来二分. //mq.clear(); s=1<<(n-m); for(x=1; x<s; x++) //建立二分数据库 { int tt=x; ll tmp=0; int cnt=0; for(i=m; i<n; i++) { if(tt&1) { tmp+=a[i]; cnt++; } tt>>=1; } nod1[x].val=tmp; nod1[x].len=cnt; } sort(nod1+1,nod1+s,cmp); nod[0].val=0; nod[0].len=0; nod[1].val=nod1[1].val; nod[1].len=nod1[1].len; p=2; for(i=2;i<s;i++) { if(nod1[i].val!=nod[p-1].val) { nod[p].val=nod1[i].val; nod[p++].len=nod1[i].len; } } sort(nod,nod+p,cmp); //for(i=0;i<p;i++) //cout<<nod[i].val<<" "<<nod[i].len<<" eh"<<endl; s=1<<m; for(x=0; x<s; x++) { ll tt=x,tmp=0; int cnt=0; for(i=0; i<m; i++) { if(tt&1) { tmp+=a[i]; cnt++; } tt>>=1; } int pos=erfen(-tmp); int pos1=max(pos-1,0),pos2=min(pos+1,p-1); for(i=pos1; i<=pos2; i++) { ll tmp1=nod[i].val+tmp; int tmp2=nod[i].len+cnt; if(tmp1==0&&tmp2==0) continue; //不能什么都不取 if(tmp1<0) tmp1=-tmp1; if(tmp1<ans||(tmp1==ans&&tmp2<res)) { ans=tmp1; res=tmp2; } } } cout<<ans<<" "<<res<<endl; } return 0; } /* 1 10 3 20 100 -100 5 5 4 1 2 3 5 5 4 -2 -2 3 0 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。