【Codeforces 922D】Robot Vacuum Cleaner

让你把n个字符串重新排序,然后按顺序连接在一起
使得这个组成的字符串的"sh"子序列最多

【题解】

```java
/*
* 假设A的情况好于B
* 也就对应了A排在B的前面
* 那么
* As*Bh>Ah*Bs ①
* 现在假设B又比C来得好
* 那么有
* Bs*Ch>Bh*Cs ②
* 由①可得
* As/Ah>Bs/Bh
* 由②可得
* Bs/Bh>Cs/Ch
* 那么有
* As/Ah>As/Ch
* 即As*Ch>Ah*As
* 也就是说A排在C的前面比较优秀
* 也就是说这个大小关系有传递性
* 那么就直接排个序就好啦,按照两两之间排序的规则来写个比较函数就好了。
*/
```
StringBuilder比直接用字符串的"+"来得快

【代码】

import java.io.*;

import java.util.*;

public class Main {

    static InputReader in;

    static PrintWriter out;

    public static void main(String[] args) throws IOException{

        //InputStream ins = new FileInputStream("E:\\rush.txt");

        InputStream ins = System.in;

        in = new InputReader(ins);

        out = new PrintWriter(System.out);

        //code start from here

        new Task().solve(in, out);

        out.close();

    }

    static int N = (int)1e5;

    static class Task{

        class Pair{

        	int s,h,i;

        	public Pair(int s,int h,int i) {

        		this.s = s;

        		this.h = h;

        		this.i = i;

        	}

        }

        public void solve(InputReader in,PrintWriter out) {

            Pair a[] = new Pair[N+10];

            String s[] = new String[N+10];

            int n;

        	n = in.nextInt();

        	for (int i = 1;i <= n;i++) {

        		s[i] = in.next();

        		int ss = 0,hh = 0;

        		for (int j = 0;j < (int)s[i].length();j++) {

        			char key = s[i].charAt(j);

        			if (key=='s') ss++;

        			if (key=='h') hh++;

        		}

        		a[i] = new Pair(ss,hh,i);

        	}

        	Arrays.sort(a, 1,n+1,new Comparator<Pair>() {

				@Override

				public int compare(Pair A, Pair B) {

					// TODO Auto-generated method stub

					long As,Ah,Bs,Bh;

					As = A.s;Ah = A.h;

					Bs = B.s;Bh = B.h;

					long temp1 =As*Bh;long temp2 =Ah*Bs;

					if (temp1>temp2) {

						return -1;

					}else if (temp1==temp2) {

						return 0;

					}else {

						return 1;

					}

				}

			});

        	StringBuilder sb = new StringBuilder();

        	for (int i = 1;i <= n;i++) {

        		sb.append(s[a[i].i]);

        	}

        	String v = sb.toString();

        	n = v.length();

        	long ans = 0;

        	long cnts = 0;

        	for (int i = 0;i < n;i++) {

        		if (v.charAt(i)=='s') {

        			cnts++;

        		}else if (v.charAt(i)=='h'){

        			ans = ans + cnts;

        		}

        	}

        	out.println(ans);

        }

    }

    static class InputReader{

        public BufferedReader br;

        public StringTokenizer tokenizer;

        public InputReader(InputStream ins) {

            br = new BufferedReader(new InputStreamReader(ins));

            tokenizer = null;

        }

        public String next(){

            while (tokenizer==null || !tokenizer.hasMoreTokens()) {

                try {

                tokenizer = new StringTokenizer(br.readLine());

                }catch(IOException e) {

                    throw new RuntimeException(e);

                }

            }

            return tokenizer.nextToken();

        }

        public int nextInt() {

            return Integer.parseInt(next());

        }

    }

}

巴特西

【Codeforces 922D】Robot Vacuum Cleaner

最新文章

热门文章