题目描述
给定一个长度为 n 的正整数数列 a1,a2,…,an 和一个正整数 k。
你可以对数列进行以下两种操作:
+ i x
,增加操作,将 ai 的值增加 x(x≥1)。
- i x
,减少操作,将 ai 的值减少 x(x≥1)。
要求:在任何时候,你都需要保证每个 ai 的值都是正整数。
请你使用尽可能少的操作次数,使得数列能够满足:对于所有 i(1≤i<n),ai+1−ai=k 均成立。
请你输出所需要的最少操作次数以及对应的具体操作方案。
输入格式
第一行包含两个整数 n,k。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
第一行输出一个整数 p,表示所需要的最少操作次数。
接下来 p 行,用来输出具体操作方案,每行输出一个具体操作 + i x
或 - i x
。你需要保证输出的 i 和 x 均为正整数,且 1≤i≤n。
如果最少操作次数的方案不唯一,则输出任意一种方案均可。
数据范围
前 3 个测试点满足 1≤n≤7。
所有测试点满足 1≤n≤1000,1≤k≤1000,1≤ai≤1000。
样例
输入样例1:
4 1
1 2 1 5
输出样例1:
2
+ 3 2
- 4 1
输入样例2:
4 1
1 2 3 4
输出样例2:
0
输入样例3:
7 1
1 1 2 3 4 5 6
输出样例3:
6
+ 2 1
+ 3 1
+ 4 1
+ 5 1
+ 6 1
+ 7 1
算法1
(贪心+枚举)
首先,对于一个正常数列,一定存在解。(即:对于所有的数字做多次操作,一定存在正确答案)
但是这样子的解一定不是最优的,那么不难发现对n个数字都操作一次,也一定会有正确答案。
于是,可以发现,一个数列中,如果以一个数字做不动标准,对于其他某些或所有数字做变化,也一定能满足题干要求。所以,对于任何一个n个数字的数列,做n-1次操作,一定是能达到要求的,至于最优解,则需要判断所有数字都做一次不动标准,来枚举剩下数字满足要求的情况,并求得最优解。
work(int k,bool flag=false)其中第二维参数,如果调用时传入参数则会使用,反之则不会
{
int res=0;
1、当前如果不动数字为第k个数字时,循环枚举除当前位的所有其他数字在满足m的公差的前提下,应为的值
for(int i=1;i<=n;i++)
{
int b=a[k]+(i-k)*m;
if(b<=0) return n;//计算得到的值如果不为正整数则返回不影响最优解统计的某个数字
2、如果当前值和计算的值相同,则不动,否则记录当前操作数res++
if(b!=a[i])
{
res++;
3、如果函数调用时传入falg为true,则表明本次枚举的答案就是最优解,于是需要同时输出方案
if(flag)
{
if(b>a[i]) printf("+ %d %d\n",i,b-a[i]);
else printf("- %d %d\n",i,a[i]-b);
}
}
}
}
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1100;
int a[N];
int n,m;
int work(int k,bool flag=false)
{
int res=0;
for(int i=1;i<=n;i++)
{
int b=a[k]+(i-k)*m;
if(b<=0) return n;
if(b!=a[i])
{
res++;
if(flag)
{
if(b>a[i]) printf("+ %d %d\n",i,b-a[i]);
else printf("- %d %d\n",i,a[i]-b);
}
}
}
return res;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
int res=n;
for(int i=1;i<=n;i++)
res=min(res,work(i));
cout<<res<<endl;
for(int i=1;i<=n;i++)
if(res==work(i))
{
work(i,true);
break;
}
return 0;
}