AcWing 4780. 等差数列-从O(n*n)优化到O(nlogn)
原题链接
中等
作者:
氘ba-wt
,
2022-12-12 22:38:20
,
所有人可见
,
阅读 173
//暴力枚举第一个数,使得数列等差,看调整次数最少的过程就是答案
//O(1000*1000)
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N], n, k;
int main(){
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
int mintimes = n, firstdata = 0;
for(int i = 1; i <= 1000; i++){
int t = 0;
for(int j = 1; j <= n; j++){
if(a[j] != i + (j - 1) * k) t++;
}
if(t < mintimes) mintimes = t, firstdata = i;
}
cout << mintimes << endl;
for(int i = 1; i <= n; i++){
if(a[i] < firstdata + (i - 1) * k) printf("+ %d %d\n", i, (firstdata + (i - 1) * k) - a[i]);
else if(a[i] > firstdata + (i - 1) * k) printf("- %d %d\n", i, a[i] - (firstdata + (i - 1) * k));
}
return 0;
}
//优化,如果调整到10万,可以先将每个数减去(i - 1) * k,
//因为最终需要等差为k,先减去后,只要保证最后能够相等即可
//看调整哪一个数的调整次数最少,只要排序看哪个正数数字出现次数最多(剩下的调整次数就最少);
//最后输出方案,即调整到这个相等数加减多少即可。
//O(nlogn)
#include<bits/stdc++.h>
using namespace std;
const int N = 1005, INF = 0x3f3f3f3f;
int a[N], b[N], n, k;
int main(){
cin >> n >> k;
for(int i = 1; i <= n; i++){cin >> b[i]; a[i] = (b[i] -= (i - 1) * k);}
sort(a + 1, a + n + 1);
int num = INF, maxlen = 0, t = 1;
for(int i = 2; i <= n; i++){
if(a[i] == a[i - 1]){
t++;
}else{
if(a[i - 1] > 0 && maxlen < t) num = a[i - 1], maxlen = t;
t = 1;
}
}
if(a[n] > 0 && maxlen < t) num = a[n], maxlen = t;
cout << n - maxlen << endl;
for(int i = 1; i <= n; i++){
if(b[i] < num) printf("+ %d %d\n", i, num - b[i]);
else if(b[i] > num) printf("- %d %d\n", i, b[i] - num);
}
return 0;
}
tql优化算法,膜拜大佬