CF1256（div3 java题解）

A：

题意：给定A个N元，B个一元，问是否可以凑成S元。

思路：A*i+j=S 即 A*I<=S<=A*I+B 即min(S/N,A)+B>=S；

/*
@author nimphy
@create 2019-11-05-10:34
about：CF1256A
*/

import java.util.*;

public class CF1256 {
    public static void main(String[] args) {
        Scanner In = new Scanner(System.in);
        int Q, A, B, N, S;
        Q = In.nextInt();
        while (Q-- > 0) {
            A = In.nextInt();
            B = In.nextInt();
            N = In.nextInt();
            S = In.nextInt();
            int I = Math.min(S / N, A) * N;
            //System.out.println(I);
            if (I + B >= S) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}

View Code

B：

题意：给定一个排列，现在让你做一套操作，使得字典序最小。

思路：贪心，先尽量把1提到前面，然后是2....，如果满足{位置交换没用过，而且比左边的小就换}

/*
@author nimphy
@create 2019-11-05-11:34
about：CF1256B
*/

import java.util.*;

public class CF1256 {
    static int[] a = new int[1010];
    static boolean[] vis = new boolean[1010];

    public static void main(String[] args) {
        Scanner In = new Scanner(System.in);

        int Q, N;
        Q = In.nextInt();
        while (Q-- > 0) {
            N = In.nextInt();
            for (int i = 1; i <= N; i++) {
                a[i] = In.nextInt();
                vis[i] = false;
            }
            for (int i = 1; i <= N; i++) {
                int pos=0;
                for (int j = 1; j <= N; j++) {
                    if (a[j] == i) {
                        pos = j;
                        break;
                    }
                }
                while (pos > i && !vis[pos]&&a[pos]<a[pos-1]) {
                    int t = a[pos];
                    a[pos] = a[pos - 1];
                    a[pos - 1] = t;
                    vis[pos] = true;
                    pos--;
                }
            }
            for (int i = 1; i <= N; i++) {
                System.out.print(a[i]+" ");
            }
            System.out.println();
        }
    }
}

View Code