贪心-字典序最小

电玩女神 2023-07-17 11:21 22阅读 0赞

问题描述：  
给定一个长度为n的字符串S，构造一个字符串T，长度也为n；起初，T是一个空字符串，随后反复进行以下操作：  
1、从S的头部删除一个字符，加到T的尾部。  
2、从S的尾部删除一个字符；加到T的尾部。  
目标是：最后生成的字符串T的字典序尽可能小。

**String** 是字符串,它的比较用compareTo方法,它从第一位开始比较,如果遇到不同的字符,则马上返回这两个字符的ascii值差值…返回值是int类型

import java.util.Scanner;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner scanner=new Scanner(System.in);
            int N=scanner.nextInt();
            StringBuilder ss=new StringBuilder();
            for (int i = 0; i <N ; i++) {
        
                ss.append(scanner.next());
            }
            f(ss.toString());
    
        }
        public static void f(String s){
        
            String s1=new StringBuilder(s).reverse().toString();
            int N=s.length();
            StringBuilder rs=new StringBuilder();
            int cnt=0;
            while (rs.length()<N){
        
                if (s.compareTo(s1)<=0){
        
                    rs.append(s.charAt(0));
                    s=s.substring(1);
                }else {
        
                    rs.append(s1.charAt(0));
                    s1=s1.substring(1);
                }
                if (rs.length()%80==0){
        
                    System.out.println(rs.substring(cnt*80,(cnt+1)*80));
                    cnt++;
                }
            }
            if (rs.length()>cnt*80){
        
                System.out.println(rs.substring(cnt*80));
            }
        }
    }