A15852 | Halve or Subtract
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
You have an array of positive integers $a_1, a_2, \ldots, a_n$ , of length $n$ . You are also given a positive integer $b$ .
You are allowed to perform the following operations (possibly several) times in any order:
1. Choose some $1 \le i \le n$ , and replace $a_i$ with $\lceil \frac{a_i}{2} \rceil$ . Here, $\lceil x \rceil$ denotes the smallest integer not less than $x$ .
2. Choose some $1 \le i \le n$ , and replace $a_i$ with $\max(a_i - b, 0)$ .
However, you must also follow these rules:
- You can perform at most $k_1$ operations of type 1 in total.
- You can perform at most $k_2$ operations of type 2 in total.
- For all $1 \le i \le n$ , you can perform at most $1$ operation of type 1 on element $a_i$ .
- For all $1 \le i \le n$ , you can perform at most $1$ operation of type 2 on element $a_i$ .
The cost of an array is the sum of its elements. Find the minimum cost of $a$ you can achieve by performing these operations.
You are allowed to perform the following operations (possibly several) times in any order:
1. Choose some $1 \le i \le n$ , and replace $a_i$ with $\lceil \frac{a_i}{2} \rceil$ . Here, $\lceil x \rceil$ denotes the smallest integer not less than $x$ .
2. Choose some $1 \le i \le n$ , and replace $a_i$ with $\max(a_i - b, 0)$ .
However, you must also follow these rules:
- You can perform at most $k_1$ operations of type 1 in total.
- You can perform at most $k_2$ operations of type 2 in total.
- For all $1 \le i \le n$ , you can perform at most $1$ operation of type 1 on element $a_i$ .
- For all $1 \le i \le n$ , you can perform at most $1$ operation of type 2 on element $a_i$ .
The cost of an array is the sum of its elements. Find the minimum cost of $a$ you can achieve by performing these operations.
输入格式
Input consists of multiple test cases. The first line contains a single integer $t$ , the number of test cases ( $1 \le t \le 5000$ ).
The first line of each test case contains $n$ , $b$ , $k_1$ , and $k_2$ ( $1 \le n \le 5000$ , $1 \le b \le 10^9$ , $0 \le k_1, k_2 \le n$ ).
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ describing the array $a$ ( $1 \le a_i \le 10^9$ ).
It is guaranteed the sum of $n$ over all test cases does not exceed $5000$ .
The first line of each test case contains $n$ , $b$ , $k_1$ , and $k_2$ ( $1 \le n \le 5000$ , $1 \le b \le 10^9$ , $0 \le k_1, k_2 \le n$ ).
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ describing the array $a$ ( $1 \le a_i \le 10^9$ ).
It is guaranteed the sum of $n$ over all test cases does not exceed $5000$ .
输出格式
For each test case, print the minimum cost of $a$ you can achieve by performing the operations.
输入输出样例
输入 #1
7 3 2 1 1 9 3 5 2 1 2 0 1000000000 1 5 3 1 1 2 8 3 19 3 6 9 4 2 1 2 3 4 5 6 3 10 3 3 1 2 3 5 1 0 0 999999999 999999999 999999999 999999999 999999999 5 5 4 3 5 9 10 7 4
输出 #1
11 500000001 23 6 0 4999999995 6
In the first test case, you can do the following:
- Perform operation 2 on element $a_3$ . It changes from $5$ to $3$ .
- Perform operation 1 on element $a_1$ . It changes from $9$ to $5$ .
After these operations, the array is $a = [5, 3, 3]$ has a cost $5 + 3 + 3 = 11$ . We can show that this is the minimum achievable cost.
In the second test case, note that we are not allowed to perform operation 1 more than once on $a_1$ . So it is optimal to apply operation 1 once to each $a_1$ and $a_2$ . Alternatively we could apply operation 1 only once to $a_1$ , since it has no effect on $a_2$ .
In the third test case, here is one way to achieve a cost of $23$ :
- Apply operation 1 to $a_4$ . It changes from $19$ to $10$ .
- Apply operation 2 to $a_4$ . It changes from $10$ to $7$ .
After these operations, $a = [2, 8, 3, 7, 3]$ . The cost of $a$ is $2 + 8 + 3 + 7 + 3 = 23$ . We can show that this is the minimum achievable cost.
- Perform operation 2 on element $a_3$ . It changes from $5$ to $3$ .
- Perform operation 1 on element $a_1$ . It changes from $9$ to $5$ .
After these operations, the array is $a = [5, 3, 3]$ has a cost $5 + 3 + 3 = 11$ . We can show that this is the minimum achievable cost.
In the second test case, note that we are not allowed to perform operation 1 more than once on $a_1$ . So it is optimal to apply operation 1 once to each $a_1$ and $a_2$ . Alternatively we could apply operation 1 only once to $a_1$ , since it has no effect on $a_2$ .
In the third test case, here is one way to achieve a cost of $23$ :
- Apply operation 1 to $a_4$ . It changes from $19$ to $10$ .
- Apply operation 2 to $a_4$ . It changes from $10$ to $7$ .
After these operations, $a = [2, 8, 3, 7, 3]$ . The cost of $a$ is $2 + 8 + 3 + 7 + 3 = 23$ . We can show that this is the minimum achievable cost.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted