游游的元素修改

[编程题]游游的元素修改

热度指数：979 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

游游拿到了一个数组，她每次操作可以使得一个元素加1，另一个元素减1。
游游希望最终数组的每个元素大小都在[l,r]范围内，她想知道自己最少多少次操作可以达成目标？

输入描述:

第一行输入一个正整数，代表用例的组数。
对于每组用例：
第一行输入三个正整数。
第二行输入个正整数，代表游游拿到的数组。



保证所有的的总和不超过。

输出描述:

输出行，每行一个整数，含义如下：
如果无法用有限次数的操作次数使得每个元素大小都在[l,r]范围内，请输出-1。
否则输出一个整数，代表最少的操作次数。

示例1

输入

输出

-1
1

说明

第一组用例：显然无法用有限次数的操作使得所有元素范围都在[3,5]之间。
第二组用例：使第一个数加1，第三个数减1即可，数组变成[4,6,4]，满足所有元素不小于4，不大于6。

算法知识视频讲解

MoonHoplite

注意到操作后数组和保持不变，如果数组和 s < l * n 或 s > r * n，则无论如何操作也不能成功，直接返回 -1。

如果 l * n <= s <= r * n，则一定可以操作。

操作可以分为两类：

1. 将某个大于 r 的数 -1，某个小于 l 的数 +1

2. 将某个大于 r 的数 -1（或小于 l 的数 +1），某个 l 到 r 之间的数 +1（或 -1）

贪心的想，操作1比较划算，因此尽量多做。具体选择哪个数并不重要，只要记录大于 r 的数需要的操作次数 s_r 和小于 l 的数需要的操作次数 s_l，做 min(s_r, s_l) 次操作1，再做 max(s_r, s_l) - min(s_r, s_l) 次操作2。因此总操作数为 max(s_r, s_l)。

t = int(input())
 
def read_nums():
    return list(map(int, input().split()))
 
for _ in range(t):
    n, l, r = read_nums()
    nums = read_nums()
 
    s = sum(nums)
    if s > r * n&nbs***bsp;s < l * n:
        print(-1)
        continue
     
    s_l, s_r = 0, 0
 
    for x in nums:
        if x > r:
            s_r += x - r
        elif x < l:
            s_l += l - x
 
    ans = max(s_l, s_r)
       print(ans)

发表于 2025-02-07 16:34:32 回复(0)

银色子弹1412

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--)
    {
        long long int n, l, r;
        cin >> n >> l >> r;
        vector<int> vec(n);
        for (int i = 0; i < n; i++)
            cin >> vec[i];
        long long int minAdd = 0, maxAdd = 0, minSub = 0, maxSub = 0;
        for (int i : vec)
        {
            if (i > r)
                minSub += i - r;
            if (i > l)
                maxSub += i - l;
            if (i < l)
                minAdd += l - i;
            if (i < r)
                maxAdd += r - i;
        }
        if (minSub > maxAdd || minAdd > maxSub)
            cout << -1 << endl;
        else
            cout << max(minSub, minAdd) << endl;
    }
}

发表于 2024-10-09 19:56:19 回复(0)

OneNiP

#include <bits/stdc++.h>
using namespace std;
int k,n,l,r;
vector<int> v;
void print(vector<int>v){
for(int i=0;i<n;i++)cout<<v[i]<<' ';
cout<<endl;
}
typedef long long int64 ;
int main() {
cin>>k;
while(k--){
cin>>n>>l>>r;
v.resize(n);
for(int i=0;i<n;i++)cin>>v[i];
sort(v.begin(),v.end());
// print(v);
// for(int i=0;i<n;i++)cout<<valid(v[i])<<' ';
int res=0;
int i=0,j=n-1;
if(v[i]>r||v[j]<l){
cout<<-1<<endl;
continue;
}
int64 a=0,b=0,c=0,asum=0,bsum=0,csum=0;
for(int i=0;i<n;i++){
int e=v[i];
if(e<l){
asum+=l-e;
a++;
}else if(e>r){
csum+=e-r;
c++;
}else {
b++;
bsum+=e-l;
}
}
// cout<<a<<asum<<endl;
// cout<<b<<bsum<<endl;
// cout<<c<<csum<<endl;
if(csum<asum){
if(asum-csum<=bsum+c*(r-l) ){
cout<<asum<<endl;
}
else cout<<-1<<endl;
}
else if(csum>asum){
if(csum-asum<=(a+b)*(r-l) -bsum){
cout<<csum<<endl;
}
else cout<<-1<<endl;
}
else {
cout<<asum<<endl;
}
}
}
// 64 位输出请用 printf("%lld")

发表于 2024-06-25 11:26:24 回复(0)