自动搬运

查看原文

来自洛谷，原作者为

	liruixiong0101 当我们身陷无尽黑暗，不妨努力绽放光亮，搏一搏，让别人看到我们身上的微光，这是给予彼此的希望。

搬运于2025-08-24 22:46:20，当前版本为作者最后更新于2023-04-10 13:52:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P1 题意：

给你 $n$ 个数 $a_1,a_2,\dots,a_n$ 和一个数 $k$，还有一个变量 $sum$，$sum$ 初始值为 $0$。你可以改变数组顺序，使从左往右遍历 $a_i$，每次遍历 $sum$ 的值加上 $a_i$，问你遍历到什么时候，$sum\notin [-2^{k-1},2^{k-1})$。

P2 思路：

我们首先就可以想到一直拿最小的，超出范围就停止循环。但是 $a_i$ 可能取负数，可能加到后面就下溢了，然后就可以想到要先加没有选的大于等于零的数中最小的，若会上溢，就加上一个没有选的负数中最大的这样减去的值就会最小，一直这样循环直到全部用完或者溢出为止。

P3 细节：

我们可以用两个数组来分别保存数小于零或大于等于零的情况。

//a数组是保存小于零的情况，b数组是保存大于等于零的情况。
for(int i = 1 , x; i <= n; i++){
	cin >> x;
	if(x < 0) a[++ta] = x;
	else b[++tb] = x;
}

但是这样还不够因为 $a,b$ 数组都初始值为 $0$ 所以会导致 $sum$ 一直加零的情况，会导致 RE，所以我们可以先把 $a,b$ 数组先赋成一个极值让 $sum$ 一加就爆，可以用 memset 做这件事。

//0xc0赋成最小值，0x3f赋成最大值。
memset(a , 0xc0 , sizeof(a));
memset(b , 0x3f , sizeof(b));

P4 代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n , k , ta , tb;
int a[N] , b[N];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0) , cout.tie(0);
	cin >> n >> k;
	memset(a , 0xc0 , sizeof(a));
	memset(b , 0x3f , sizeof(b));
	for(int i = 1 , x; i <= n; i++){
		cin >> x;
		if(x < 0) a[++ta] = x;
		else b[++tb] = x;
	}
	sort(a + 1 , a + 1 + ta , greater<int>());
	sort(b + 1 , b + 1 + tb);
	//贪心若这个数大于等于零先选最小的，否则先选最大的。
	int s1 = 1 , s2 = 1 , sum = 0 , ans = 0;
	while(s1 <= tb || s2 <= ta){
		if(sum + b[s1] < (1 << (k - 1))){
			sum += b[s1++];
		}//若sum没有上溢。
		else if(sum + a[s2] >= -(1 << (k - 1))){
			sum += a[s2++];
		}//若sum上溢了，但是没有下溢。
		else break;//否则直接停止循环。
		ans++;
	}
	cout << ans;
	return 0;
}