java：P1088 [NOIP2004 普及组] 火星人

java：P1088 [NOIP2004 普及组] 火星人

洛谷题目：P1088 [NOIP2004 普及组] 火星人

题目如下： 思路一：

全排列后找到火星人表示的排序，然后再往后排序m次即可。
看了下数据，肯定超时，放弃。

思路二：

改进思路一，直接在全排列中找到外星人的排序。
可以试试

我的代码：

import java.io.*;

public class Main {
    static int n;
    static int m;
    static boolean bool = true;
    static int ct = 0;
    static int[] ints;          // 对比用的
    static boolean[] pd;        // 看intz【】是否被征用
    static int[] cc;            // 存储当前的数据
    static StringBuilder str = new StringBuilder();
    static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in = new StreamTokenizer(ins);
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException{
        in.nextToken();
        n = (int)in.nval;
        in.nextToken();
        m = (int)in.nval;
        ints = new int[n+1];
        pd = new boolean[n+1];
        cc = new int[n];
        for(int i = 1;in)
        {
            bool = false;
            if(m==0)
            {
                for(int i = 0;i 
测试结果： 
 
看了下卡的数据，实在是太大了
 
 10000
 82
 9574 5427 4149 828 1608 281 7437 7078 6021 7963 855 3510 ……
 
最多压了10000个栈，java顶不住了
 
Exception in thread "main" java.lang.StackOverflowError
 
只能搞模拟，可是我看别人的c++就能过啊，气人啊！
 
思路三 
 
 
搞模拟，看大佬的思路
 
 
大佬思路：
 
 
代码实现： 
import java.io.*;

public class Main{
    static StringBuilder str = new StringBuilder();
    static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in = new StreamTokenizer(ins);
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException{
        in.nextToken();
        int n = (int)in.nval;
        in.nextToken();
        int m = (int)in.nval;
        int[] ints = new int[n];
        for(int i =0;i=1;m--)
        {
            for(j = n-1;j>=0;j--)
            {
                if(ints[j]>ints[j-1])
                {
                    break;
                }
            }
            j--;
            for(k = n-1;k>j;k--)
            {
                if(ints[k]>ints[j])
                {
                    break;
                }
            }
            ints[j] ^= ints[k];
            ints[k] ^= ints[j];
            ints[j] ^= ints[k];
            j++;
            k = n-1;
            while(j 
 
 
1、模拟去重的全排列，好东西啊！一定要会！！在数据过大时肯定有用。
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5564329.html