算法2
(暴力枚举) $O(n^2)$
思路:扫描一下最长的不用改变的序列,标记一下,后面再特判一下。。。。。。。,我以后看可能会迷糊,我自己都不知道怎么过的。。。
java 代码
import java.io.*;
import java.io.BufferedReader;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.nio.ByteBuffer;
import java.nio.charset.StandardCharsets;
import java.text.Format;
import java.text.SimpleDateFormat;
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Map;
import java.util.HashMap;
public class Main {
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static StringBuilder stringBuilder = new StringBuilder();
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static String s = "";
static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
static int n = 0;
static int min = (int) 2e9;
static int sum = 0;
static long sum1 = 0;
static int max = -1;
static int m1=0;
static int m2=0;
static int m3=0;
static int m = 0;
static int ans = 0;
static int l = 0;
static int r = 0;
StringBuilder stringBuilder1=new StringBuilder();
static Map<Map<Integer,Integer> ,Integer> map= new TreeMap<Map<Integer, Integer>, Integer>();
static Map<Integer,Integer> map1= new TreeMap<>();
static Map<Integer,Integer> map2= new TreeMap<>();
static Map<String,Integer> map3= new TreeMap<>();
static int[] h = new int[(int) (5e+5)];
static boolean[] booleans=new boolean[101];
static int[][] b2 = new int[1000][1000];
static int[] dp = new int[10005];
static int[][] pd = new int[55][55];
static int[][] fs = new int[6][6];
static int[] a=new int[1050];
static int[] f=new int[2022];
static int[] b=new int[1005];
static int[] a1={0,1,-1,0,0};
static int[] b1={0,0,0,1,-1};
static int[] a2={0,1,-1,1,-1,2,-2,-2,2};
static int[] c2={0,2,2,-2,-2,-1,-1,1,1};
static String[] s1=new String[1005];
static Set<String> set=new TreeSet<>();
static Stack<String> stack=new Stack<>();
static Queue<Integer> queun=new LinkedList<Integer>();//单队列
static Deque<Integer> deque=new ArrayDeque<>();//双队列
static PriorityQueue<Integer> xiao = new PriorityQueue();
static PriorityQueue<Integer> xiao1 = new PriorityQueue();
static PriorityQueue<Integer> xiao2 = new PriorityQueue();
static PriorityQueue<Integer> da_1 = new PriorityQueue(Collections.reverseOrder());
static PriorityQueue<Long> da = new PriorityQueue(Collections.reverseOrder());
public static void main(String[] args) throws IOException {
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
Scanner sc=new Scanner(System.in);
//sc.hasNext();
// sc.next();
n=Scanf_Int();
m=Scanf_Int();
for (int i=1;i<=n;i++){
a[i]=Scanf_Int();
f[i]=a[i];
}
for (int i=2;i<=n;i++){
m1=i;
while (a[m1]>=(1+(i-1)*m)&&a[m1]-a[m1-1]==m){
b[i-1]++;
m1++;
}
if (b[i-1]>max){
max=b[i-1];
ans=i-1;
m2=a[i-1];
}
}
int t = a[1];
if (max==0){
for (int i=1;i<=n;i++){
a[1]=i;
for (int k=2;k<=n;k++){
a[k]=f[k];
}
int count1=0;
for (int j=2;j<=n;j++){
if (a[j] - a[j - 1] == m) {
continue;
}
count1++;
a[j] = a[j - 1] + m;
}
if (count1<min){
min=count1;
l=i;
}
}
}
int count = 0;
if (max==0){
if (t!=l){
min++;
}
a[1]=l;
}
else {
a[1] = m2 - (ans - 1) * m;
}
if(min==n) {
a[1]=t;
min--;
}
if (a[1] < t) {
count++;
stringBuilder.append("- " + 1 + " " + (t - a[1])).append("\n");
m3 = 520;
} else if (a[1] > t) {
count++;
stringBuilder.append("+ " + 1 + " " + (a[1] - t)).append("\n");
m3 = 520;
}
for (int k=2;k<=n;k++){
a[k]=f[k];
}
for (int i = 2; i <= n; i++) {
if (a[i] - a[i - 1] == m) {
continue;
}
if (a[i] - a[i - 1] < m) {
m3 = 520;
count++;
stringBuilder.append("+ " + i + " " + (a[i - 1] + m - a[i])).append("\n");
} else if (a[i] - a[i - 1] > m) {
m3 = 520;
count++;
stringBuilder.append("- " + i + " " + Math.abs(a[i - 1] + m - a[i])).append("\n");
}
a[i] = a[i - 1] + m;
}
if (m3 != 520) {
out.println(0);
} else {
if (max==0){
out.println(min);
}
else {
out.println(count);
}
out.print(stringBuilder);
}
out.close();
}
static int Scanf_Int() throws IOException {
in.nextToken();
return (int) in.nval;
}
static long Scanf_Long() throws IOException {
in.nextToken();
return (long) in.nval;
}
static double Scanf_Double() throws IOException{
in.nextToken();
return in.nval;
}
static char Scanf_Char()throws IOException{//输入字符后可以空格,也可以换行
in.nextToken();
return in.sval.charAt(0);
}
static String Scanf_String() throws IOException{
/*
***输入的字符串有空格的不能用这个***
不能用这个来转变为字符数组和字符串数组,用bf.readLine();
输入字符串后可以空格,也可以换行*/
in.nextToken();
return in.sval;
}
}
class Node implements Comparable<Node> {
int q,w;
double e;
String s;
String s1;
public Node(String s, String s1) {
this.s = s;
this.s1 = s1;
}
public Node( String s,int q, int w) {
this.q = q;
this.w = w;
this.s = s;
}
public Node(int q, int w) {
this.q = q;
this.w = w;
}
public Node(int q, String s) {
this.q = q;
this.s = s;
}
public Node(int q, int w, double e) {
this.q = q;
this.w = w;
this.e = e;
}
@Override
public int compareTo(Node o) {
if (o.q==this.q){
return this.w-o.w;
}
else {
return this.q-o.q;
}
}
}
class Node1 implements Comparable<Node1>{
int t,l,r,x;
long f;
String s;
public Node1( long f,int l) {
this.l = l;
this.f = f;
}
public Node1(int l, int r) {
this.l = l;
this.r = r;
}
public Node1(int t, int x, String s) {
this.t = t;
this.x = x;
this.s = s;
}
@Override
public int compareTo(Node1 o) {
return o.t-this.t;
}
}
哪来的人才收藏这个???,这个。。。
估计这个没多少人看的懂
我感觉有错,但是过了