免费代刷网站推广快速,做黑帽需不需要搭建网站,中国交通建设集团有限公司英文名,自行车网站模板题目大意 给定N#xff08;N35)个数字#xff0c;每个数字都 2^15. 其中一个或多个数字加和可以得到s#xff0c;求出s的绝对值的最小值#xff0c;并给出当s取绝对值最小值时#xff0c;需要加和的数字的个数。 题目分析 需要枚举集合的所有情况#xff0c;2^35… 题目大意 给定NN35)个数字每个数字都 2^15. 其中一个或多个数字加和可以得到s求出s的绝对值的最小值并给出当s取绝对值最小值时需要加和的数字的个数。 题目分析 需要枚举集合的所有情况2^35会超时。考虑使用折半枚举的方法考虑前 N/2个数字构成的集合S1在S1中进行所有情况枚举复杂度为 2^17并将所有可能的和sum以及构成和sum需要的数字个数count存放在map M中然后在S2中进行所有情况的枚举复杂度为2^17对于每种情况的sum2在M中查找 -sum2的位置在该位置前后位置处进行查找求和的最小值。 还需要考虑当s只有S1中的数字构成或者s只有S2中的数字构成或者s由S1和S2中的数字构成的三类情况。 总的时间复杂度为 O(2^17 2^17*log(2^17)) O(2^22) 实现(c) #includestdio.h
#includestring.h
#includealgorithm
#includestring
#includecmath
#includeiostream
#includemap
using namespace std;long long int ll_abs(long long int n){if (n 0)return n;return -n;
}
long long int an[40];maplong long int, int sum_map;
int main2(){int n;while (scanf(%d, n) n){maplong long int, int::iterator it;sum_map.clear();for (int i 0; i n; i){scanf(%lld, an[i]);}long long int min_sum ll_abs(an[0]);int min_count 1;int m n / 2;for (int i 0; m 0 i (1 m); i){long long int sum 0;int count 0;int t i;for (int k 0; k m; k){if (t 1){sum an[k];count;}t 1;}if (count 0)continue;if (sum_map.find(sum) ! sum_map.end()){sum_map[sum] min(sum_map[sum], count);}elsesum_map[sum] count;if (ll_abs(sum) min_sum){min_sum ll_abs(sum);min_count count;}else if (ll_abs(sum) min_sum){min_count min(min_count, count);}}m n / 2 n % 2;for (int i 0; i (1 m); i){long long int sum 0;int count 0;int t i;for (int k 0; k m; k){if (t 1){sum an[n / 2 k];count;}t 1;}if (count 0)continue;if (ll_abs(sum) min_sum){min_sum ll_abs(sum);min_count count;}else if (ll_abs(sum) min_sum){min_count min(min_count, count);}it sum_map.lower_bound(-sum);if (it ! sum_map.end()){long long int s sum it-first;if (ll_abs(s) min_sum){min_sum ll_abs(s);min_count it-second count;}else if (ll_abs(s) min_sum){min_count min(min_count, it-second count);}}if (it ! sum_map.begin()){--it;long long int s sum it-first;if (ll_abs(s) min_sum){min_sum ll_abs(s);min_count it-second count;}else if (ll_abs(s) min_sum){min_count min(min_count, it-second count);}}}printf(%lld %d\n, min_sum, min_count);}return 0;
}转载于:https://www.cnblogs.com/gtarcoder/p/4909448.html
