涟源市建设局网站,软件开发和网站开发难度,高端品牌网站建设的特点,百度游戏中心app一、题目大意
我们有N#xff08;N35#xff09;个元素#xff0c;从中选取一个子集#xff0c;使得它的元素求和的绝对值最小#xff0c;如果有多个可行解#xff0c;选择元素最小的。
输出最优子集的元素总和绝对值#xff0c;和最优子集元素的数量。
二、解题…一、题目大意
我们有NN35个元素从中选取一个子集使得它的元素求和的绝对值最小如果有多个可行解选择元素最小的。
输出最优子集的元素总和绝对值和最优子集元素的数量。
二、解题思路
我们把前一半后一半数组分开考虑。
我们利用二进制递增的思路0001,0010,0011...1111把后一半数组的所有子集求和给算出来去掉空集同时记录每个子集的元素数量。
之后根据子集的sum进行排序然后利用双指针把所有sum相等的子集的元素数量更新为 同等sum下最小的元素数量。
然后利用二进制枚举前半部分数组包括空集对于每一个左半部分的元素和leftSum去后半部分数组里二分找 -leftSum这个二分的思想就是找到后半部分最小子集元素和不小于 -leftSum的第一个下标然后把二分的结果idx和idx-1都判断下计算左右子集和的绝对值和元素数量。更新ans。
需要注意的是我们去掉了右边为空集的情况所以要额外判断下只使用左边元素的情况。
我也是很菜了这个题目WA了60多次写了6天最后绝对不用pair了自己写结构体也不用lower_bound了自己写二分然后再结合自己想出来的尺取法过了这道题。
过程中没有查看题解没有搜过答案但是去看了STL中pair的源码和Comparator的源码还看了下《挑战程序设计》的“超大背包问题”的源码其实不应该去看这些影响到了进步和思考的进程看完STL源码和白书后决定不用pair和lower_bound了手写二分底层实现手写双指针优化终究是过了。 可以说我是非常菜了自己摸爬滚打总结的一套代码分享在下面。
过了以后查过题解我这个他们那个map那个复杂一些因为用了自定义结构体双指针和手写二分底层实现但是比它快了5倍吧源码分享给大家。
三、代码
#include iostream
#include algorithm
using namespace std;
typedef long long ll;
struct Node
{int cnt;ll sum;Node(ll sum 0LL, int cnt 0) : sum(sum), cnt(cnt) {}
};
Node rightNodes[262150];
int towPow[27], n, rightLen, leftLen, rightPow, leftPow, ansCnt;
ll num[40], ans, inf 0x3f3f3f3f3f3f3f3fLL;
void initTwoPow()
{towPow[0] 1;for (int i 1; i 21; i){towPow[i] towPow[i - 1] * 2;}
}
bool compareNode(const Node a, const Node b)
{return a.sum b.sum;
}
ll absVal(ll a)
{if (a 0LL){return a;}else{return a * (-1LL);}
}
void input()
{ans 0LL;for (int i 0; i n; i){scanf(%lld, num[i]);ans ans num[i];}ans absVal(ans);ansCnt n;leftLen n / 2;rightLen n - leftLen;leftPow towPow[leftLen];rightPow towPow[rightLen];
}
void calcRightSubsetBesideEmptySet()
{for (int i 1; i rightPow; i){rightNodes[i - 1].sum 0LL;rightNodes[i - 1].cnt 0;for (int j 0; j rightLen; j){if ((i towPow[j]) towPow[j]){rightNodes[i - 1].sum rightNodes[i - 1].sum num[leftLen j];rightNodes[i - 1].cnt rightNodes[i - 1].cnt 1;}}}rightNodes[rightPow - 1].sum inf;rightNodes[rightPow - 1].cnt n 1;sort(rightNodes, rightNodes rightPow, compareNode);
}
void minimizeCntByTwoPosinter()
{int l 0, r 1, optCnt -1;while (true){while (r rightPow rightNodes[r].sum ! rightNodes[l].sum){l;r;}optCnt rightNodes[l].cnt;while (r rightPow rightNodes[r].sum rightNodes[l].sum){optCnt min(optCnt, rightNodes[r].cnt);r;}while ((l 1) r){rightNodes[l].cnt optCnt;}if (r rightPow){break;}}
}
int binarySearch(ll leftSum)
{int l -1, r rightPow;while (l 1 r){int mid (l r) / 2;if (rightNodes[mid].sum leftSum){l mid;}else{r mid;}}return (l 1);
}
void solve()
{ll lSum 0LL;int lCnt 0;for (int i 0; i leftPow; i){lSum 0LL;lCnt 0;for (int j 0; j leftLen; j){if ((i towPow[j]) towPow[j]){lSum lSum num[j];lCnt lCnt 1;}}if (lCnt ! 0 absVal(lSum) ans){ans absVal(lSum);ansCnt lCnt;}else if (lCnt ! 0 absVal(lSum) ans lCnt ansCnt){ansCnt lCnt;}int idx binarySearch(lSum * (-1LL));if ((idx 1) rightPow absVal(rightNodes[idx].sum lSum) ans){ans absVal(rightNodes[idx].sum lSum);ansCnt rightNodes[idx].cnt lCnt;}else if ((idx 1) rightPow absVal(rightNodes[idx].sum lSum) ans (rightNodes[idx].cnt lCnt) ansCnt){ansCnt rightNodes[idx].cnt lCnt;}idx--;if (idx 0 absVal(rightNodes[idx].sum lSum) ans){ans absVal(rightNodes[idx].sum lSum);ansCnt rightNodes[idx].cnt lCnt;}else if (idx 0 absVal(rightNodes[idx].sum lSum) ans (rightNodes[idx].cnt lCnt) ansCnt){ansCnt rightNodes[idx].cnt lCnt;}}
}
int main()
{initTwoPow();while (true){scanf(%d, n);if (n 0){break;}input();calcRightSubsetBesideEmptySet();minimizeCntByTwoPosinter();solve();printf(%lld %d\n, ans, ansCnt);}return 0;
}
