P9207 灭罪「正直者之死」 题解

· · 题解

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;
}