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

张开发
• 2026/4/13 12:27:03 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

打卡信奥刷题（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输入 #16 1000 1 2 999 4 72 6输出 #12输入输出样例 #2输入 #210 2 2 1 2 2 1 1 2 2 2 2输出 #23输入输出样例 #3输入 #31 1 1输出 #30说明/提示【样例解释 #1】将a3a_3a3​修改为333a5a_5a5​修改为555。【数据范围】本题采用捆绑测试。Subtask 1202020分n2n 2n2w2w 2w2。Subtask 2202020分n,w≤100n, w \leq 100n,w≤100。Subtask 3101010分ai1a_i 1ai​1。Subtask 4202020分n,w≤1000n, w \leq 1000n,w≤1000。Subtask 5303030分没有特殊限制。对于100%100 \%100%的数据1≤n,w≤3×1051 \leq n, w \leq 3 \times 10^51≤n,w≤3×105。原始 ideaix35。C实现#includeiostreamusingnamespacestd;intn,w,ans;inta[300005],c[300005],t[300005];intmain(){cinnw;if(n1){cout0;return0;}for(inti1;in;i)cina[i];ansn;for(intk0;1(n-1)*kw;k){for(inti1;in;i)if(a[i]-k*(i-1)0a[i]-k*(i-1)(n-1)*kw)t[a[i]-k*(i-1)],ansmin(ans,n-t[a[i]-k*(i-1)]);for(inti1;in;i)if(a[i]-k*(i-1)0)t[a[i]-k*(i-1)]0;}coutans;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容

更多文章