网站模板哪个好,wordpress 建点,芜湖网络,昆明网络营销Eels
题目链接#xff1a;luogu CF1098D
题目大意
有一个可重集#xff0c;每次操作会放进去一个数或者取出一个数。 然后每次操作完之后#xff0c;问你对这个集合进行操作#xff0c;每次选出两个数 a,b 加起来合并回去#xff0c;直到集合中只剩一个数#xff0c;要…Eels
题目链接luogu CF1098D
题目大意
有一个可重集每次操作会放进去一个数或者取出一个数。 然后每次操作完之后问你对这个集合进行操作每次选出两个数 a,b 加起来合并回去直到集合中只剩一个数要你最小化 2ab 或 2ba 的次数。 每次输出这个最小次数。
思路
有一个简单的贪心结论是每次选最小的两个合并。 感性理解就是你如果要贡献了那迟早都要贡献你这里加了说不定他就够大了就不一定在下一次贡献了。
接下来发现你这样这题好像还不能过。 于是考虑再推一点结论发现它贡献的条件我们还没有用上。 于是考虑一下这个二倍会发现一个什么问题就是如果你某一次要贡献。 比如贡献的形式是 x,yx,yx,y其中 2xy2xy2xy那你其实会发现这个 yyy 是不可能是被合并出来的它一定是原生的。
那如果它能被合出来 y1y2y(y1⩽y2)y_1y_2y(y_1\leqslant y_2)y1y2y(y1⩽y2)那我们每次合最小的两个那 y1,y2y_1,y_2y1,y2 已经被合了 xxx 还在那一定有 y1⩽y2⩽xy_1\leqslant y_2\leqslant xy1⩽y2⩽x那 y1y2⩽2xy_1y_2\leqslant 2xy1y2⩽2x 即 y⩽2xy\leqslant 2xy⩽2x 与 y2xy2xy2x 矛盾。 也不难看出当 kxykxykxy 为条件的时候两个推出来的条件分别是 y⩽2xy\leqslant 2xy⩽2x 与 ykxykxykx也就是当 k⩾2k\geqslant 2k⩾2 的时候其实这个结论都成立这也是这个条件成立的充要条件。
那这个说明什么你如果要出现贡献大的一定是原生的而每次你都会合最小的两个那要让大的是原生的也就是它是现在第二小的而且比它大的里面不应该有非原生的。 因为有的话就说明它肯定没有最小的二倍。 那最小的肯定就是原生的里面比他小的和。 那条件就是先把数组排序在让 sumi∑x1iaxsum_i\sum\limits_{x1}^ia_xsumix1∑iax ∑i1n[2sumi−1ai]\sum\limits_{i1}^n[2sum_{i-1}a_i]i1∑n[2sumi−1ai] 那我们要做的就是在插入数和删去数的过程中维护这个东西的值。 会发现问题在于每个地方都要判断一次但是一个显然的事情是每一次是上次的两倍以上那每次这个值都会翻倍那就只会有至多 log\loglog 次贡献。 那你会发现如果你按最高位的存在来分我们对于每个维护一个 set那你会发现每一组至多只有一个贡献那我们需要判断的次数也缩小到了 log\loglog 级别就可以了。
代码
#includeset
#includecstdio
#define ll long longusing namespace std;int n, ans;
multiset int s[36];
ll sum[36];int getk(int x) {int re 0;while (x 1) re, x 1;return re;
}int main() {scanf(%d, n);while (n--) {char c getchar(); while (c ! c ! -) c getchar();int x; scanf(%d, x);int k getk(x);if (c -) {s[k].erase(s[k].find(x));sum[k] - x;}if (c ) {s[k].insert(x);sum[k] x;}ll Sum 0; ans 0;for (int i 0; i 30; i)if (s[i].size()) {ans s[i].size();if ((*s[i].begin()) 2 * Sum) ans--;Sum sum[i];}printf(%d\n, ans);} return 0;
}
