打卡信奥刷题（3105）用C++实现信奥题 P7273 ix35 的等差数列

P7273 ix35 的等差数列

题目背景

等差数列是指从第二项起，每一项与它的前一项的差等于同一个常数的一种数列，并称这个常数为公差。特别地，认为只有一项的数列也是等差数列，其公差视为000。

题目描述

给定一包含nnn项的正整数列a1,a2,…,ana_1, a_2, \ldots , a_na1​,a2​,…,an​，满足1≤ai≤w1 \leq a_i \leq w1≤ai​≤w。

现可以进行若干次修改，一次修改可将数列的任意一项修改为任意≤w\leq w≤w的正整数。

求：至少进行多少次修改，才能使得原数列变为一公差为非负整数的等差数列。

输入格式

第一行两个整数n,wn, wn,w。
接下来一行nnn个整数a1,a2,…,ana_1, a_2, \ldots , a_na1​,a2​,…,an​。

输出格式

一行一个整数，所求答案。

输入输出样例 #1

输入 #1

6 1000 1 2 999 4 72 6

输出 #1

2

输入输出样例 #2

输入 #2

10 2 2 1 2 2 1 1 2 2 2 2

输出 #2

3

输入输出样例 #3

输入 #3

1 1 1

输出 #3

0

说明/提示

【样例解释 #1】

将a3a_3a3​修改为333，a5a_5a5​修改为555。

【数据范围】

本题采用捆绑测试。

• Subtask 1（202020分）：n=2n = 2n=2，w=2w = 2w=2。
• Subtask 2（202020分）：n,w≤100n, w \leq 100n,w≤100。
• Subtask 3（101010分）：ai=1a_i = 1ai​=1。
• Subtask 4（202020分）：n,w≤1000n, w \leq 1000n,w≤1000。
• Subtask 5（303030分）：没有特殊限制。

对于100%100 \%100%的数据，1≤n,w≤3×1051 \leq n, w \leq 3 \times 10^51≤n,w≤3×105。

原始 idea：ix35。

C++实现

#include<iostream>usingnamespacestd;intn,w,ans;inta[300005],c[300005],t[300005];intmain(){cin>>n>>w;if(n==1){cout<<0;return0;}for(inti=1;i<=n;i++)cin>>a[i];ans=n;for(intk=0;1+(n-1)*k<=w;k++){for(inti=1;i<=n;i++)if(a[i]-k*(i-1)>0&&a[i]-k*(i-1)+(n-1)*k<=w)t[a[i]-k*(i-1)]++,ans=min(ans,n-t[a[i]-k*(i-1)]);for(inti=1;i<=n;i++)if(a[i]-k*(i-1)>0)t[a[i]-k*(i-1)]=0;}cout<<ans;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容