序列最小化题解
序列最小化
https://ac.nowcoder.com/acm/contest/5556/C
思路：贪心
这道题没什么太难的地方，因为是1-n的序列，所以最后肯定是都变为1.
那我们首先需要找1的位置，然后判断把左右都变为1需要多少次。
首先把左边的元素个数/（k-1），因为每次也要把1包含进去，所以要-1.
然后我们通过（（k-1）-p%（k-1））%（k-1）计算需要移动的位置。
%（k-1）是为了防止1在首位。
然后再判断右边需要变化的次数即可。
import java.util.*;
import java.math.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.PrintWriter;
public class Main {
public static void main(String args[])throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
in.nextToken();
int n = (int) in.nval;
in.nextToken();
double k = (int) in.nval;
int num[] = new int[n];
int p=0;
if(n==k)
out.print(1);
else
{
for(int i=0;i<n;i++)
{
in.nextToken();
num[i] = (int) in.nval;
if(num[i]==1)
p = i;
}
double q=0,o=0;
double sum=0;
sum += Math.ceil(p/(k-1));
q = ((k-1)-p%(k-1))%(k-1);
sum += Math.ceil((n-1-p-q)/(k-1));
out.println((long)sum);
}
out.flush();
}
} 
虾皮信息成长空间 250人发布
