B. 爱丽丝国际象棋历险记 time limit per test: 1 seconds memory limit per test: 256 megabytes input:…
- User
B. 爱丽丝国际象棋历险记
time limit per test: 1 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output
题目描述
爱丽丝正在参加疯帽子的茶会!有一个由 个部分组成的长条蛋糕,美味值为 。茶会上有 个生物,不包括爱丽丝。
爱丽丝会将蛋糕切成 块。从形式上看,她会将蛋糕分割成 个子数组,其中每个子数组由一定数量的相邻部分组成。一块蛋糕的美味程度是其各部分美味程度的总和。之后,她会把这些 块分给 个生物和她自己(她的块可以是空的)。然而,只有当每个 生物的美味度达到或超过 时,它们才会感到快乐。
爱丽丝希望确保每个生物都快乐。受限于这个条件,她也想最大限度地提高自己棋子的美味度。你能帮爱丽丝找出她的棋子的最大美味吗?如果无法确保每个生物都快乐,则输出 。
输入格式
每个测试包含多个测试用例。第一行包含测试用例的数量 ( )。测试用例说明如下。
每个测试用例的第一行都包含三个整数 ( ;{55091636})。( ; ) - 分别是章节数量、生物数量和生物对美味的最低要求。
下一行包含 个空格分隔的整数 ( ) --各部分的美味程度。
所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,输出爱丽丝的作品所能达到的最大美味度,如果无法确保每个生物都满意,则输出 。
样例 #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提示
注
对于第一个测试案例,爱丽丝可以把第一和第二部分作为自己的作品,然后把剩下的 美味占为己有。我们可以证明,她不可能做得更好。
对于第二个测试案例,爱丽丝可以把第一和第二部分作为一块,把第六部分作为一块。这样,她就可以把剩下的 份美味占为己有。我们可以证明她不可能做得更好。
在第七个测试案例中,爱丽丝不能给每个生物至少 的美味。
用c++写,注意不要范围,不要越界
- Assistant
To solve the problem efficiently, we need to find the maximum possible sum that Alice can assign to herself while ensuring that all
mcreatures receive blocks of the cake with sums at leastv. 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:
-
Prefix Sum Calculation:
- Compute the prefix sums to easily calculate the sums of any subarray in constant time.
-
Compute Maximum Blocks on Left and Right:
- Left Count (
left_count): For each positioni, calculate the maximum number of non-overlapping blocks with sum ≥vfrom the start up to positioni. - Right Count (
right_count): Similarly, for each positioni, calculate the maximum number of non-overlapping blocks with sum ≥vfrom positionito the end.
- Left Count (
-
Binary Search:
- Use binary search to determine the maximum possible sum
Xthat Alice can take. - For each
X, check if there exists a contiguous block[l, r]with sum ≥Xsuch that the remaining sections of the cake can be divided intomblocks each with sum ≥v. - The binary search narrows down the potential values of
Xby continuously checking the feasibility of the current midpoint and adjusting the search range based on the result.
- Use binary search to determine the maximum possible sum
-
Verification:
- During each binary search iteration, use a sliding window technique to identify valid blocks
[l, r]with sum ≥Xand verify whether the remaining parts can fulfill the required number of blocks.
- During each binary search iteration, use a sliding window technique to identify valid blocks
-
Edge Cases:
- If the total sum of the cake is insufficient to satisfy all creatures (
m * v), output-1.
- If the total sum of the cake is insufficient to satisfy all creatures (
-
Output:
- After identifying the suitable
X, the answer isXitself, which represents the maximum sum Alice can take for her block.
- After identifying the suitable
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"; } } } -