Codeforces 922 C - Robot Vacuum Cleaner (贪心、数据结构、sort中的cmp，建模+分析思维)

几天跟着队长做的一套题，太菜了啊，要好好努力啊

http://codeforces.com/problemset/problem/922/D

题意： 给一堆由s和h组成的字符串，让你拼接，使得子序列为“sh”的数量最多，并且输出这个最多的值

开始以为这种题是用dp写的（以前模拟训练写到有类似于：多个字符串，每个字符串可以反转，反转一次要花一定得价值，反转后会有一定得价值，问最多能有多少得价值，这题目是典型得dp，开dp[i][2]，表示前i个字符串：0表示不反转，1，表示反转的妆台得到的价值，不断转移前面的价值，最后得出答案：ans=max(dp[n][0],dp[n][1])）,但是这题，设计字符串的拼接和组合，组合多样化，并不像前面那题字符串的拼接顺序是一样的，那么观察了一下样例，好像都是s多的在前面哦，但是这样的想法是错的。s,h单关键量排序在前在后都不是正确的。然后又仔细分析了一下，如果对于一个字符串，其内部的”sh“个数是一样的，那么对于这个串的贡献=自己内部的子串+这个字符串中的h值*前面所有的s个数，然而每个自己内部的个数是固定的，交换顺序只改变相乘的部分。那么问题转化为求外部的sh串个数。那么我们随便想一想，这个串前面尽可能的多s，后面尽可能得小h，如果单单以s大排序或h小排序都不行，那么就用s/h得关键词来排序（这是一个贪心题目结构体排序中重要得一种模型）。所以随便排下序好了。坑点：当一个小块中h得个数为0时，直接设为inf

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#include<map>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<string.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=100006;
struct node{
 string s;
 ll a,b;
 ll num;
 double val;
}s[maxn];

ll cmp(node a,node b){
 return a.val >b.val ;
}

int main(){
 ll n;
 cin>>n;
 for(ll i=0;i<n;i++){
  s[i].a=s[i].b=0;
  cin>>s[i].s ;
  s[i].num=0;
  ll cnt=0;
  ll size=s[i].s.size ();
  for(int k=0;k<size;k++){
   if(s[i].s[k]=='s'){
    s[i].a++;
    cnt++;
   }
   else{
    s[i].b++;
    s[i].num+=cnt;
   }
  }
  if(s[i].b==0)s[i].val =inf;
  else s[i].val=s[i].a*1.0/s[i].b;
 }
 sort(s,s+n,cmp);
 string ss="";
 ll ans=0;
 ll pre=0;
 for(int i=0;i<n;i++){
  ss+=s[i].s;
  ans+=s[i].num +s[i].b*pre;
  pre+=s[i].a ;
 }
 printf("%lld\n",ans);
}

//希望自己天天都有所长进啊！！！