千元低价网站建设,注册公司取名字,网站app搭建,vs网站毕业设计怎么做链接#xff1a; http://poj.org/problem?id3977 题意#xff1a; 给你n个数#xff0c;n最大35#xff0c;让你从中选几个数#xff0c;不能选0个#xff0c;使它们和的绝对值最小 如果有一样的#xff0c;取个数最小的 题解#xff1a; np难题#xff0c;但是因为…链接 http://poj.org/problem?id3977 题意 给你n个数n最大35让你从中选几个数不能选0个使它们和的绝对值最小 如果有一样的取个数最小的 题解 np难题但是因为数据小所以可以通过折半枚举求解 先枚举前一半的所有情况 用map记录下来 然后在枚举后一半的所有情况再在前一半记录的map里面找相加的和 与0最接近的 开始我用的set但是set不好处理重复的 不过map居然也可以用lower_bound 另外poj好像不支持long long的abs 所以要自己写一个 代码 1 #include map2 #include set3 #include cmath4 #include queue5 #include stack6 #include cstdio7 #include string8 #include vector9 #include cstdlib
10 #include cstring
11 #include sstream
12 #include iostream
13 #include algorithm
14 #include functional
15 using namespace std;
16 #define rep(i,a,n) for (int ia;in;i)
17 #define per(i,a,n) for (int in-1;ia;i--)
18 #define pb push_back
19 #define mp make_pair
20 #define all(x) (x).begin(),(x).end()
21 #define SZ(x) ((int)(x).size())
22 typedef vectorint VI;
23 typedef long long ll;
24 typedef pairint, int PII;
25 const ll MOD 1e9 7;
26 const int INF 0x3f3f3f3f;
27 const double EPS 1e-10;
28 const double PI acos(-1.0);
29 const int MAXN 8010;
30 // head
31
32 ll list[40];
33 map ll, int mm;
34 typedef pairll, int pli;
35
36 ll labs(ll x) {
37 return x 0 ? x : -x;
38 }
39
40 int main() {
41 int n;
42 while (cin n, n) {
43 mm.clear();
44 rep(i, 0, n) scanf(%lld, list i);
45 pli ans mp(1e18, 0);
46 int n1 n / 2, n2 n - n1;
47 rep(i, 1, 1 n1) {
48 ll sum 0;
49 int num 0;
50 rep(j, 0, n1) if (i(1 j)) sum list[j], num;
51 if (!mm[sum] || mm[sum] num) mm[sum] num;
52 pli t mp(labs(sum), num);
53 if (t ans) ans t;
54 }
55 rep(i, 1, 1 n2) {
56 ll sum 0;
57 int num 0;
58 rep(j, 0, n2) if (i(1 j)) sum list[n1 j], num;
59 pli t mp(labs(sum), num);
60 if (t ans) ans t;
61 mapll, int::iterator k mm.lower_bound(-sum);
62 if (k ! mm.end()) {
63 t mp(labs((*k).first sum), num (*k).second);
64 if (t ans) ans t;
65 }
66 if (k ! mm.begin()) --k;
67 if (k ! mm.end()) {
68 t mp(labs((*k).first sum), num (*k).second);
69 if (t ans) ans t;
70 }
71 }
72 cout ans.first ans.second endl;
73 }
74 return 0;
75 } 转载于:https://www.cnblogs.com/baocong/p/6693060.html
