修改后的和

本题采用多组案例输入，第一行一个整数 $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$ 中至少有一个非负整数

C++(g++ 7.5.0) 解法, 执行用时: 98ms, 内存消耗: 1168K, 提交时间: 2023-06-11 16:25:26

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
     
int main()
{
  int t,n,m;
  int i;
  ll a[100010];
  cin>>t;
  while(t--)
  {
  	cin>>n>>m;
	ll ans=0;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		ans+=a[i];
		a[i]*=(ll)(n+1-i);
	}
	sort(a+1,a+1+n);
	reverse(a+1,a+1+n);
	for(i=1;i<=min(n,m);i++)
	{
		if(a[i]>0)
		{
			ans-=a[i];
		}
	}
	cout<<ans<<endl;
  }
  return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 100ms, 内存消耗: 1144K, 提交时间: 2023-06-11 21:27:43

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m,n,sum;
ll a[200001];
int main()
{
   int t;
   cin>>t;
   while(t--){
cin>>n>>m;
  ll sum=0;
for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i],a[i]=a[i]*(n-i+1);
sort(a+1,a+1+n);
for(int i=n;i>n-m;i--){
	if(a[i]>0) sum-=a[i];
	else break;
}
cout<<sum<<endl;
}

    return 0;
}

pypy3 解法, 执行用时: 302ms, 内存消耗: 34216K, 提交时间: 2023-06-09 21:44:11

for i in range(int(input())):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = []
    for i in range(n):
        if a[i] > 0:
            b.append(-a[i] * (n - i))
    b.sort()
    print(sum(a) + sum(b[:min(len(b), m)]))

Python3 解法, 执行用时: 290ms, 内存消耗: 16636K, 提交时间: 2023-06-27 11:08:36

T=int(input())
for _ in range(T):
    n,m=map(int,input().split())
    arr=list(map(int,input().split()))
    tmp=[]
    for i in range(n-1,-1,-1):
        if arr[i]>0:
            tmp.append(-arr[i]*(n-i))
    tmp.sort()
    print(sum(arr)+sum(tmp[:m]))

详情