【枚举】CF978 D

朱雀 2024-03-22 20:47 59阅读 0赞

[Problem - D - Codeforces][]

题意：

![8f99fdca19694799b0a369ce6b953909.png][]

![66a9cc03b2854ec68f6bf9a67176cc14.png][]

思路：

所谓枚举，就是要利用隐含条件找出不明显的小数据，即状态数很少

这道题中，因为是等差数列，且每个数只能被+1或-1一次

确定了前两个数和公差之后，数列就被确定了

而公差只有3种情况，前两个数只有9种情况

那么只需要O(9N)枚举即可

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    
    int N;
    int a[mxn],b[mxn];
     
    int calc(int d){
    	memcpy(b,a,sizeof(b));
    	int res=0;
    	for(int i=3;i<=N;i++){
    		if(b[i]-b[i-1]>d+1||b[i]-b[i-1]<d-1) return 1e9;
    		if(b[i]-b[i-1]==d+1){
    			res++;
    			b[i]--;
    		}else if(b[i]-b[i-1]==d) continue;
    		else{
    			res++;
    			b[i]++;
    		}
    	}
    	return res;
    }
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	int D=a[2]-a[1],d=D;
    	int ans=1e9;
    	for(int i=-1;i<=1;i++){
    		for(int j=-1;j<=1;j++){
    			a[1]+=i;
    			a[2]+=j;
    			ans=min(ans,calc(a[2]-a[1])+(i!=0)+(j!=0));
    			a[1]-=i;
    			a[2]-=j;
    		}
    	}
    	if(ans==1e9) cout<<-1<<'\n';
    	else cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - D - Codeforces]: https://codeforces.com/contest/978/problem/D
[8f99fdca19694799b0a369ce6b953909.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/d27b39fc7f4b467f82d398a5be529e8d.png
[66a9cc03b2854ec68f6bf9a67176cc14.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/24a1d79f55ac4798a39e3ababa44182b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，59人围观）

还没有评论，来说两句吧...

相关阅读

相关【枚举】CF1660 D

[Problem - 1660D - Codeforces][] 题意： ![208a35e52d4f4427a5e8eabf77f136e7.png][] 思路：思

缺乏、安全感/ 2024年03月23日 21:52/ 0 赞/ 51 阅读

相关【枚举】CF1706 C

有人一道1400写了一个小时 [Problem - C - Codeforces][] 题意： ![24af41cf246b45db9ced0751c3617969.p

Myth丶恋晨/ 2024年03月23日 19:27/ 0 赞/ 44 阅读

相关【枚举，构造】CF1582 C D

[Problem - C - Codeforces][] 题意： ![41aba6a6704a46188f11720ce4b622e5.png][] ![35a7376c

旧城等待，/ 2024年03月23日 18:48/ 0 赞/ 73 阅读

相关【枚举+01 trie树】CF1658 D2

[Problem - D2 - Codeforces][] 题意：给定一个区间\[l, r\]和r - l + 1个数，问是否存在一个数 x ，使得这些数异或上 x 之后

绝地灬酷狼/ 2024年03月23日 18:02/ 0 赞/ 42 阅读

相关【枚举边+树的直径】CF14D

[Problem - 14D - Codeforces][] 题意： ![fe2da99906ca4bcd9783bdf0d72af0ca.png][] ![9f9007

比眉伴天荒/ 2024年03月23日 00:23/ 0 赞/ 71 阅读

相关【枚举】CF978 D

[Problem - D - Codeforces][] 题意： ![8f99fdca19694799b0a369ce6b953909.png][] ![66a9cc03

朱雀/ 2024年03月22日 20:47/ 0 赞/ 60 阅读

相关【枚举】CF1833 D

[Problem - D - Codeforces][] 题意：给定一个序列，让你找一个区间，翻转区间内的数，交换前缀和后缀，让结果数组的字典序最大 ![c14db1d

深碍√TFBOYSˉ_/ 2024年03月22日 19:49/ 0 赞/ 79 阅读

相关【枚举+数学】CF1781D Many Perfect Squares

n很小时，可以考虑双指针看看有没有什么性质 [Many Perfect Squares - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][Many Perf

谁践踏了优雅/ 2024年03月22日 15:30/ 0 赞/ 46 阅读

相关【枚举+DS】CF1831D

不懂，m d，挂着再说 [Problem - D - Codeforces][] 题意： ![13d3e88892634f35907141b95608275c.png][

红太狼/ 2024年03月16日 10:41/ 0 赞/ 24 阅读

相关【*1500 枚举】CF1487D

又到了日常写水题环节.... 感觉这题只有\1300.... [Problem - D - Codeforces][] 题意：给定N 问你存在多少个三元组(a,b,

àì夳堔傛蜴生んèń/ 2024年03月16日 10:35/ 0 赞/ 47 阅读