目录

1026、程序运行时间（分数 15）

1027、打印沙漏（分数 20）

1028、人口普查（分数 20）

1029、旧键盘（分数 20）

1030、完美数列（分数 25）

1026、程序运行时间（分数 15）

题目描述：

代码实现：

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        long C1 = in.nextLong();
        long C2 = in.nextLong();
        long res = Math.round((C2 - C1) / 100.0);
        long h = res / 3600;
        long m = (res - 3600 * h) / 60;
        long s = res % 60;
        System.out.printf("%02d:%02d:%02dn", h, m, s);
    }
}

运行结果：

---

1027、打印沙漏（分数 20）

题目描述：

代码实现：

import java.util.Scanner;

public class Main{
    public static void trans(int num, int D){
        if (num != 0){
            trans(num / D, D);
            System.out.print(num % D);
        }
    }

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int A = in.nextInt();
        int B = in.nextInt();
        int D = in.nextInt();
        if(A + B == 0){
            System.out.println("0");
            return;
        }
        trans(A + B,D);
        System.out.println();
    }
}

运行结果：

---

1028、人口普查（分数 20）

题目描述：

代码实现：

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int[] count = new int[11];
        StringBuffer res = new StringBuffer();
        boolean firstFlag = false;
        for(int i = 0;i < 10;i ++)      count[i] = in.nextInt();
        in.close();
        for(int i = 1;i < 10;i ++){
            if(!firstFlag && count[i] != 0){
                res.append(String.valueOf(i));
                for(int k = 0;k < count[0];k ++)    res.append("0");
                count[i] --;
                firstFlag = true;
            }
            
            if(firstFlag && count[i] != 0){
                for(int j = 0;j < count[i];j ++){
                    res.append(String.valueOf(i));
                }
            }
        }
        System.out.println(res);
    }
}

运行结果：

---

1029、旧键盘（分数 20）

题目描述：

代码实现：

利用一下正则表达式... ...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String txt = bf.readLine();
        String pattern = bf.readLine();
        bf.close();
        List broken = new ArrayList<>();
        for (int i = 0; i < txt.length(); i++) {
            String s = txt.substring(i, i+1);
            if (!pattern.contains(s)){
                if (!broken.contains(s) && !broken.contains(s.toLowerCase()) && !broken.contains(s.toUpperCase()))
                    broken.add(s);
            }
        }
        for (String b : broken) {
            if (b.matches("[a-z]"))       System.out.print(b.toUpperCase());
            else System.out.print(b);
        }
        System.out.println();
    }
}

运行结果：

---

1030、完美数列（分数 25）

题目描述：

代码实现：

这题需把题意理一下：

1.找出数列的一个子数列使其最大值M和最小值m满足M <= mp

2.这个子数列里包含的元素尽可能多

一个解决思路为：

先将数列整个排序，再设立两个指针 i 和 j 分别从数组第一个位置、数组最后一个位置开始，

这样 i~j 所划分的区间即是一个子数列，且i、j指向的元素分别为子数列最小、最大值，这样一旦满足 M <= mp 条件就记录下该子数列的元素个数，用二维数组count[][]来存取， 并且有，不满足 M <= mp 条件则深搜一遍，在i < j的前提下对i + 1 ~ j、i ~ j - 1两个区间作同样处理。

最后枚举一遍count[ ][ ]找出最大值。

---

Java代码实现出来如下： 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main{

    public static void dfs(long[] nums, int i, int j, int[][] count, long p){
        if(nums[j] <= nums[i] * p){      //找到解
            count[i][j] = j - i + 1;
            return;
        }
        if(i < j){
            dfs(nums, i + 1, j, count, p);
            dfs(nums, i, j - 1, count, p);
        }
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] line1 = bf.readLine().split(" ");
        int N = Integer.parseInt(line1[0]);
        long p = Long.parseLong(line1[1]);
        String[] line2 = bf.readLine().split(" ");
        bf.close();
        long[] nums = new long[N];
        for(int i = 0;i < N;i ++){
            nums[i] = Long.parseLong(line2[i]);
        }
        Arrays.sort(nums);
        int[][] count = new int[N][N];
        dfs(nums, 0, N - 1, count, p);
        int max = count[0][0];
        for(int i = 0;i < N;i ++)
            for(int j = 0;j < N;j ++)
                max = Math.max(max, count[i][j]);
        System.out.println(max);
    }
}

运行结果：

---

好家伙利用了BufferedReader来读数据仍然超时，看来上述的思路用Java来实现注定又是A不了了，上C++：

由于上述思路运用于C++发现还是会超时，所以优化了一下，把这个问题抽象为滑动窗口，减去了一些不必要的区间试探。

#include 
#include 
using namespace std;
typedef long long ll;

int main(){
    ll N;
    ll p;
    scanf("%lld %lld", &N, &p);
    ll nums[N];
    for(int i = 0;i < N;i ++){
        scanf("%lld", &nums[i]);
    }
    sort(nums, nums + N);
    int count = 0;
    //滑动窗口，下一次滑动的窗口大小 >= 上一次窗口大小
    for(int i = 0;i < N;i ++){  
        for(int j = i + count;j < N;j ++){      //右指针可以优化位置，每次直接从上次窗口的大小开始试探，看可否再扩大（扩j）
            if(nums[j] <= p * nums[i])
                count = max(count, j - i + 1);      //每次窗口大小j - i + 1
            else    break;      //不满足说明再无希望，右指针再右移只会使最大值更大，更无可能满足条件，直接退出内循环
        }
    }
    
    cout << count << endl;
    return 0;
}

运行结果：