Skip to content
The Chat Archive
o1-mini-2024-09-12· OpenAI WildChat-4.8M (AI2)

B. 爱丽丝国际象棋历险记 time limit per test: 1 seconds memory limit per test: 256 megabytes input:…

  1. User

    B. 爱丽丝国际象棋历险记

    time limit per test: 1 seconds

    memory limit per test: 256 megabytes

    input: standard input

    output: standard output

    题目描述

    爱丽丝正在参加疯帽子的茶会!有一个由 nn 个部分组成的长条蛋糕,美味值为 a1,a2,…,ana_1, a_2, \ldots, a_n 。茶会上有 mm 个生物,不包括爱丽丝。

    爱丽丝会将蛋糕切成 m+1m + 1 块。从形式上看,她会将蛋糕分割成 m+1m + 1 个子数组,其中每个子数组由一定数量的相邻部分组成。一块蛋糕的美味程度是其各部分美味程度的总和。之后,她会把这些 m+1m + 1 块分给 mm 个生物和她自己(她的块可以是空的)。然而,只有当每个 mm 生物的美味度达到或超过 vv 时,它们才会感到快乐。

    爱丽丝希望确保每个生物都快乐。受限于这个条件,她也想最大限度地提高自己棋子的美味度。你能帮爱丽丝找出她的棋子的最大美味吗?如果无法确保每个生物都快乐,则输出 −1-1 。

    输入格式

    每个测试包含多个测试用例。第一行包含测试用例的数量 tt ( 1≤t≤1041 \le t \le 10^4 )。测试用例说明如下。

    每个测试用例的第一行都包含三个整数 n,m,vn, m, v ( 1≤m≤n≤2⋅1051\le m\le n\le 2\cdot 10^5 ;{55091636})。( 1≤m≤n≤2⋅1051\le m\le n\le 2\cdot 10^5 ; 1≤v≤1091\le v\le 10^9 ) - 分别是章节数量、生物数量和生物对美味的最低要求。

    下一行包含 nn 个空格分隔的整数 a1,a2,…,ana_1, a_2, \ldots, a_n ( 1≤ai≤1091 \le a_i \le 10^9 ) --各部分的美味程度。

    所有测试用例的 nn 之和不超过 2⋅1052\cdot 10^5 。

    输出格式

    对于每个测试用例,输出爱丽丝的作品所能达到的最大美味度,如果无法确保每个生物都满意,则输出 −1-1 。

    样例 #1

    样例输入 #1

    7
    6 2 1
    1 1 10 1 1 10
    6 2 2
    1 1 10 1 1 10
    6 2 3
    1 1 10 1 1 10
    6 2 10
    1 1 10 1 1 10
    6 2 11
    1 1 10 1 1 10
    6 2 12
    1 1 10 1 1 10
    6 2 12
    1 1 1 1 10 10
    

    样例输出 #1

    22
    12
    2
    2
    2
    0
    -1
    

    提示

    注

    对于第一个测试案例,爱丽丝可以把第一和第二部分作为自己的作品,然后把剩下的 10+1+1+10=2210 + 1 + 1 + 10 = 22 美味占为己有。我们可以证明,她不可能做得更好。

    对于第二个测试案例,爱丽丝可以把第一和第二部分作为一块,把第六部分作为一块。这样,她就可以把剩下的 10+1+1=1210 + 1 + 1 = 12 份美味占为己有。我们可以证明她不可能做得更好。

    在第七个测试案例中,爱丽丝不能给每个生物至少 1212 的美味。

    用c++写,注意不要范围,不要越界

  2. Assistant

    To solve the problem efficiently, we need to find the maximum possible sum that Alice can assign to herself while ensuring that all m creatures receive blocks of the cake with sums at least v. The approach involves using binary search to pinpoint the optimal sum Alice can take, and verifying whether such a partition is possible.

    Step-by-Step Reasoning:

    1. Prefix Sum Calculation:

      • Compute the prefix sums to easily calculate the sums of any subarray in constant time.
    2. Compute Maximum Blocks on Left and Right:

      • Left Count (left_count): For each position i, calculate the maximum number of non-overlapping blocks with sum ≥ v from the start up to position i.
      • Right Count (right_count): Similarly, for each position i, calculate the maximum number of non-overlapping blocks with sum ≥ v from position i to the end.
    3. Binary Search:

      • Use binary search to determine the maximum possible sum X that Alice can take.
      • For each X, check if there exists a contiguous block [l, r] with sum ≥ X such that the remaining sections of the cake can be divided into m blocks each with sum ≥ v.
      • The binary search narrows down the potential values of X by continuously checking the feasibility of the current midpoint and adjusting the search range based on the result.
    4. Verification:

      • During each binary search iteration, use a sliding window technique to identify valid blocks [l, r] with sum ≥ X and verify whether the remaining parts can fulfill the required number of blocks.
    5. Edge Cases:

      • If the total sum of the cake is insufficient to satisfy all creatures (m * v), output -1.
    6. Output:

      • After identifying the suitable X, the answer is X itself, which represents the maximum sum Alice can take for her block.

    Implementation:

    Below is the C++ code implementing the above logic:

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    
    // Function to check if for a given X, there exists a window [l, r] with sum >= X
    // and the remaining can be split into m blocks with sum >=v
    bool check_feasible(int n, int m, int v, const vector<ll>& a, const vector<int>& left_count, const vector<int>& right_count, ll X) {
        int l = 1, r = 1;
        ll current_sum = 0;
        while (l <= n) {
            // Expand the window to the right until sum >= X
            while (r <= n && current_sum < X) {
                current_sum += a[r];
                r++;
            }
            if (current_sum >= X) {
                // Check if the left and the right parts can provide m blocks
                // Left part is [1, l-1], right part is [r, n]
                // Note: right_count is 1-based, and r is the next position after the window
                int total_blocks = 0;
                if (l - 1 >= 0) {
                    total_blocks += left_count[l - 1];
                }
                if (r <= n) {
                    total_blocks += right_count[r];
                }
                if (total_blocks >= m) {
                    return true;
                }
            }
            // Move the window forward by removing a[l]
            current_sum -= a[l];
            l++;
        }
        return false;
    }
    
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin >> t;
        while(t--){
            int n, m;
            ll v;
            cin >> n >> m >> v;
            // 1-based indexing
            vector<ll> a(n + 2, 0);
            for(int i=1;i<=n;i++) cin >> a[i];
            // Compute left_count
            vector<int> left_count(n + 2, 0);
            ll current_sum =0;
            int count =0;
            int start =1;
            for(int i=1;i<=n;i++){
                current_sum +=a[i];
                if(current_sum >=v){
                    count +=1;
                    left_count[i] = count;
                    current_sum =0;
                }
                else{
                    left_count[i] = count;
                }
            }
            // Compute right_count
            vector<int> right_count(n + 2, 0);
            current_sum =0;
            count =0;
            for(int i=n;i>=1;i--){
                current_sum +=a[i];
                if(current_sum >=v){
                    count +=1;
                    right_count[i] = count;
                    current_sum =0;
                }
                else{
                    right_count[i] = count;
                }
            }
            // Compute total_sum
            ll total_sum =0;
            for(int i=1;i<=n;i++) total_sum +=a[i];
            // Binary search
            ll low =0, high = total_sum;
            ll answer = -1;
            while(low <= high){
                ll mid = low + (high - low)/2;
                if(check_feasible(n, m, v, a, left_count, right_count, mid)){
                    answer = mid;
                    low = mid +1;
                }
                else{
                    high = mid -1;
                }
            }
            // Now, need to check if it's possible to have m blocks with sum >=v
            // If m blocks cannot be formed, output -1
            // But our binary search should already cover that
            if(answer == -1){
                // Check if m blocks with sum >=v are possible at all
                // Using left_count[n]
                if(left_count[n] < m){
                    cout << "-1\n";
                }
                else{
                    // Minimal sum is m*v, but it's not directly calculable
                    // Here, assign answer as total_sum - m*v
                    // But it's not correct, need to instead handle the case
                    // However, according to the binary search, answer=-1 only if m blocks cannot be formed
                    // So this branch might never be needed
                    cout << "-1\n";
                }
            }
            else{
                // Check the sum of Alice's block is answer
                // To maximize Alice's sum, which is answer
                // But according to the binary search, answer is the maximum possible sum Alice can have
                // So output answer
                cout << answer << "\n";
            }
        }
    }