\^_^ 还是 :-(｜二分答案

T3 - ^_^ 还是 :-(

题目链接跳转：点击跳转

一道简单的思维题目，难度定在【普及-】还算是合理的。不过 USACO 的 Bronze 组别特别喜欢考这种类似的思维题目。

普通算法

考虑采用贪心的思路，先把序列按照从大到小的原则排序。暴力枚举一个节点 $i$，判断是否有可能满足选择前 $i$ 个数字 $-1$，剩下的数字都至少 $+1$ 的情况下所有的数字都大于零。

那么该如何快速的判断是否所有的数字都大于零呢？首先可以肯定的是，后 $n - i$ 个数字一定是大于零的，因为这些数字只会增加不会减少。所以我们把重点放在前 $i$ 个数字上面。由于数组已经是有序的，因此如果第 $i$ 个数字是大于 $1$ 的，那么前 $i$ 个数字在减去 $1$ 之后也一定是正整数。

由于使用了排序算法，本算法的单次查询时间复杂度在 $O(N \log_2 N)$ 级别，总时间复杂度为 $O(N^2 \log_2 N)$，可以在 $\tt{1s}$ 内通过所有的测试点。

本题的 C++ 代码如下：

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
int arr[1005];

void solve(){
    cin >> n;
    long long sum = 0;
    for (int i=1, t; i<=n; i++){
        cin >> arr[i];
    }
    sort(arr+1, arr+1+n, greater<int>());
    if (n == 1) {
    	cout << ":-(" << endl;
        return ;
    }
    // 暴力枚举，选择前 i 个数字 - 1，剩下的所有数字都至少 + 1。
    bool flag = 0;
    for (int i=1; i<=n; i++){
        sum += arr[i];
        if (arr[i] == 1) break;
        if (sum - (n - i) >= i) flag = 1;
    }
    cout << (flag ? "^_^" : ":-(") << endl;
    return ;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while(T--) solve();
    return 0;
}

本题的 Python 代码如下：

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    
    # 对数组降序排序
    arr.sort(reverse=True)
    
    if n == 1:
        print(":-(")
        return

    # 暴力枚举前 i 个数字 - 1，剩下的数字 +1
    sum_ = 0
    flag = False
    for i in range(1, n + 1):
        sum_ += arr[i - 1]
        if arr[i - 1] == 1:
            break
        if sum_ - (n - i) >= i:
            flag = True
    
    print("^_^" if flag else ":-(")

def main():
    T = int(input())
    for _ in range(T):
        solve()

if __name__ == "__main__":
    main()

二分答案优化

注意到答案是单调的，因此可以使用二分答案的算法来适当优化。虽然效果微乎其微，但在整体时间运行上表现良好。

优化后的 C++ 代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int arr[1005];

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> arr[i];
    
    sort(arr + 1, arr + 1 + n, greater<int>());
    
    if (n == 1) {
        cout << ":-(" << endl;
        return;
    }

    int left = 1, right = n, res = -1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] > 1) {
            res = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << (res != -1 ? "^_^" : ":-(") << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

优化后的 Python 算法如下：

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    
    # 对数组降序排序
    arr.sort(reverse=True)

    if n == 1:
        print(":-(")
        return

    left, right, res = 0, n - 1, -1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] > 1:
            res = mid
            right = mid - 1
        else:
            left = mid + 1

    print("^_^" if res != -1 else ":-(")

def main():
    T = int(input())
    for _ in range(T):
        solve()

if __name__ == "__main__":
    main()