c++ - 查找数组中的最小更改数以进行 k 算术级数
问题描述
我最近遇到了这个问题:
在挑战中,您将获得一个包含 n 个数字和一个整数 k 的数组。在一分钟内,您可以将数组的任何元素更改为您想要的任何整数。求出满足以下条件的最少时间:对于所有 i 从到 1,n - 1,a[i] - a[i - 1] = k。由于 n, k <= 10^5 解决方案应该是线性的 (O(n)) 或者我怀疑的 O(n * logn)。
我贪婪地意识到这个问题可能是DP,但我找不到答案。这个主题是相似的,但那里的答案没有用(在我看来)。我只是在寻找一个伪(或 cpp)代码。
UPD:我在 O(n^2) 中编写了一个蛮力解决方案,如果它对您有帮助,这里是代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cerr.tie(nullptr);
int n, k;
cin >> n >> k;
vi a(n);
for (auto& i : a)
cin >> i;
int res = INT32_MAX;
for (int i = 0; i < n; ++i){
int s = a[i], sol = 0;
for (int j = i + 1; j < n; ++j){
s += k;
if (a[j] != s)
++sol;
}
s = a[i];
for (int j = i - 1; j > -1; --j){
s -= k;
if (a[j] != s)
++sol;
}
res = min(sol, res);
}
cout << res << '\n';
}
解决方案
我不完全确定这是否适合这里,如果我理解正确,您正在要求一种算法。
您需要找到最少数量的元素进行更改,以便满足进度。我建议你减去斜率,即a[i]-=k*i
现在你所要做的就是找到新数组中最常出现的数字(更重要的是,它出现了多少次)。基本上,你想问有多少点位于某些线上(a[i]=k*i+m),所以你减去斜率并计算每个点的出现次数m
。m
最常出现的值具有适当值的最高点数,因此我们所要做的就是修复所有其他点。
鉴于您的值可能很大(我假设),您可以使用它std::map
来进行计数,这在最坏的情况下应该会给您 O(n*log(n))。最终的结果是n-maxReps
,其中maxReps
是新数组中重复次数最多的值的重复次数。正如我们所说,我们仍然需要更改的值的数量才能满足我们的条件。
本质上,您只需计算必须修复的点数,以便它们位于您的线上。
我将把实现留给你。
推荐阅读
- powershell - Powershell - 仅获取具有值的属性
- google-apps-script - Gsheet 中的动态范围 - 在分析之前准备 GForm 数据
- go - 流服务器错误:rpc 错误:代码 = 不可用 desc = 传输正在关闭“
- android - 谷歌助手未在 Android 应用上采用新的 URI
- rest - 访问谷歌云部署的 REST API 的 URL
- css - 如何修复 Internet Explorer 中的字体错误(不使用字体)[BLAZOR]
- sql - Angular 上的 Codemirror for SQL 提示有效,但出现 Typescript 输入错误
- pagespeed-insights - Page Speed 仅第一次显示高分
- c# - 将对象转换为泛型类型实例
- flutter - AudioPlayer 搜索栏在对话框颤振中不起作用