查找所需编辑数量的数组问题

Question

给定一个包含正元素和整数 K 的数组 arr。在一个操作中，您可以选择数组的一个元素（假设 arr[i]）并中断到 p1,p2 插入 p1 和 p2。您需要找到可能的最小值。

这是我的方法：

#include <bits/stdc++.h> 
using namespace std;
int main(){
int n,k; cin >> n >> k;
vector<int>v;
for(int i=0;i<n;i++)
{
    int x; cin >> x;
    v.push_back(x);
}
while(k--)
{
    int x,y;
    sort(v.begin(),v.end());
    int p=v[v.size()-1];
    vector<int>::iterator it;
    it=v.begin()+v.size()-1; 
    v.erase(it);
    if(p%2==0)
    {
        x=p/2,y=p/2;
    }
    else
    {
        x=p/2;
        y=p-x;
    }
    v.push_back(x);
    v.push_back(y);
}
cout << *max_element(v.begin(),v.end());
return 0;
}

是否正确？如果它是正确的那么（TC是n*k）有没有可能的优化解决方案？

Answer 1

如评论中所述，您的算法无法始终提供正确答案。这是另一种算法的提议。

检查给定的最大值（=目标）是否可以在 K 操作中获得相当容易：对于每个元素 x=A[i]，计算必需的操作数 C(x)让这个特定元素变得小于目标。所需操作的总数等于各个计数的总和。我们只需要将获得的总数与 K.

进行比较

例如C(x) = sup(x/target) -1，当sup(.)等于大于或等于其输入值的最小整数时。请注意 C(0) = 0.

可以通过按降序对数组进行排序来优化对目标值有效性的检查。这允许在数组元素变得小于目标时停止计数。

最小最大值 minmax 使得 minmax 可以通过上述过程验证，但不能 minmax-1。这可以通过二进制搜索来执行。

全局复杂度：O(n log(Amax))，其中Amax是最大元素值。

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

int Count_elt (int x, int target) {
    if (x == 0) return 0;
    int count = x/target;
    if (target*count == x) count --;
    return count;
}

bool check_target (std::vector<int>& A, int K, int target) {
    int n = A.size();
    int count = 0;
    for (int val: A) {
        if ((val <= target) || count > K) break;
        count += Count_elt (val, target);
    }
    return count <= K;
}

int minmax (std::vector<int>& A, int K) {
    std::sort (A.begin(), A.end(), std::greater<int>());
    if (A[0] == 0) return 0;
    int limit_0 = 0;    // highest value such that check = false
    int limit_1 = A[0]; // lowest value such that check = true
    while (true) {
        if (limit_1 == limit_0 + 1) return limit_1;
        int target = (limit_0 + limit_1) / 2;
        bool test = check_target(A, K, target);
        if (test) {
            limit_1 = target;
        } else {
            limit_0 = target;
        }
    }
    return -1;
}

int main () {
    std::vector<int> A = {12, 3, 3, 9};
    int K = 3;
    int Count = minmax (A, K);
    std::cout << "Count = " << Count << "\n";
}

查找所需编辑数量的数组问题

array problem of finding number of edits needed

c++

arrays

minimum