补题 [NC252735] 修改后的和
1
2
3
| 时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
|
题目描述
牛牛面前有一个由 $n$ 个整数组成的数组 $A_1,A_2,…,A_n$。
牛牛打算对这个数组进行若干次操作。
每次操作牛牛可以选择 $A_1,A_2,…,A_n$ 中的任意一个非负整数，记所选数的下标为 $k$。然后牛牛会把 $A_k,A_{k+1},…,A_n$ 都减少 $A_k$。
牛牛想知道他对这个数组进行恰好 $m$ 次操作后，数组中所有数的和最少是多少。
输入描述
本题采用多组案例输入，第一行一个整数 $T$ 代表案例组数。
每组案例中，第一行输入两个空格分隔的整数 $n\ m$。
接下来一行输入 $n$ 个由空格分隔的整数代表：$A_1,A_2,…,A_n$。
保证：
$0 < n,m \leq 10^5$
$-10^6 \le A_i \le 10^6$
单个测试点中所有案例 $n$ 的和不超过 $2\times 10^5$
单组案例的 $A_1,A_2,…,A_n$ 中至少有一个非负整数
输出描述
对于每组案例，输出一行一个整数代表牛牛在进行恰好 $m$ 次操作之后数组中所有数的和的最少值。
输入
1
2
3
4
5
| 2
5 10000
-9 0 -3 -1 -10000
5 3
-10 4 9 -2 0
|
输出
说明
第一组案例只能不断地选择 $A_2$ 所以总和不变。
第二组案例一组最优选择是 [$A_3,A_2,A_2$]
数组的变化是： [-10,4,9,-2,0] —> [-10,4,0,-11,-9] —> [-10,0,-4,-15,-13] —> [-10,0,-4,-15,-13] 第二组理论上更好的方案是选择 [$A_1,A_3,A_2$]
但是由于选择 $A_1$ 时其是负数，所以这组方案不可以选择。
题解
题目解析
一道贪心题,假设我们得到了数组 [1,3,-1,5,6,3] ,那么它们每一个位置可以提供的减少量可以另外开一个数组存,即 [1*6,3*5,0,5*3,6*2,3*1] 等于 [6,15,0,15,12,3] .
我们只需要找到依据 $m$ 找到相应个数的最大减少量即可解决此问题.
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define var(size) int p[size]{}
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(a,n,p) for(int i=a;i<=n;i+=p)
#define fb(a,n,p) for(int i=a;i>=n;i-=p)
#define cin(length,var) for(int i=1;i<=length;i++) cin >> var[i]
typedef long long ll;
MAXN(1e5);
signed main(){
CIN;CIN_;
int T;
cin >> T;
while(T--){
vector<ll> p(MAXN);
ll n,m,ans=0;
cin >> n >> m;
fa(1,n,1){
cin >> p[i];
ans += p[i];
p[i] = p[i] * (n - i + 1);
}
sort(p.begin()+1, p.begin()+1+n);
reverse(p.begin()+1, p.begin()+1+n);
fa(1,min(n,m),1){
if(p[i] > 0){
ans -= p[i];
}
}
cout << ans << endl;
}
return 0;
}
|
