hihocoder61

http://hihocoder.com/contest/offers61/problems
题目1 : 最小排列

package l611;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(), m=sc.nextInt();
        List<Integer>l=new ArrayList<Integer>();
        boolean[] vis=new boolean[1+n];
        int[]a=new int[m];
        for(int i=0;i<m;i++){
            a[i]=sc.nextInt();
            vis[a[i]]=true;
        }
        int p=1;
        for(int i:a) {
            while(p<i) {
                if(!vis[p]) l.add(p);
                p++;
            }
            l.add(i);
            p=Math.max(p, i+1);
        }
        for(;p<=n;p++) l.add(p);
        for(int i:l)
            System.out.println(i);
    }
}

题目2 : 最大前缀和
数据范围比较小，直接枚举，枚举每个前缀，考虑维护两个set，一个是在前缀里的数的集合，一个是不在前缀里的数的集合。每次交换肯定是用前缀里最小的数去换不在前缀里的最大的数

package l612;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

// 数据范围比较小，直接枚举
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(), k=sc.nextInt();
        long[]a=new long[n];
        for(int i=0;i<n;i++)a[i]=sc.nextLong();
        
        long[][]min=new long[n][k], max=new long[n][k];
        for(int i=0;i<n;i++) Arrays.fill(min[i], Long.MAX_VALUE);
        for(int i=0;i<n;i++) Arrays.fill(max[i], Long.MIN_VALUE);
        PriorityQueue<Long>pq=new PriorityQueue<Long>();
        for(int i=0;i<n;i++) {
            pq.add(a[i]);
            List<Long>tmp=new ArrayList<Long>();
            for(int j=0;j<Math.min(i+1, k);j++) {
                long t = pq.remove();
                tmp.add(t);
                min[i][j]=((j==0?0:min[i][j-1])+t);
            }
            for(long t:tmp) pq.add(t);
        }
        PriorityQueue<Long>pq2=new PriorityQueue<Long>();
        for(int i=n-1;i>=0;i--) {
            pq2.add(-a[i]);
            List<Long>tmp=new ArrayList<Long>();
            for(int j=0;j<Math.min(n-i, k);j++) {
                long t = pq2.remove();
                tmp.add(t);
                max[i][j]=((j==0?0:max[i][j-1])-t);
            }
            for(long t:tmp) pq2.add(t);
        }
        
        long res = Long.MIN_VALUE, sum = 0;
        for(int i=0;i<n;i++) {
            sum += a[i];
            res = Math.max(res, sum);
            for(int j=0;j<Math.min(i+1, k);j++) {
                if(i+1<n && max[i+1][j]>min[i][j]) // 为什么这里需要额外判断一下max[i+1][j]>min[i][j]才能AC，可能是Corner case吧
                    res = Math.max(res, sum-min[i][j]+max[i+1][j]);
            }
        }
        System.out.println(Math.max(res, 0));
    }
}