D. Robot Vacuum Cleaner(贪心,排序)

$其实还是比较玄学的做法,所有即使想到一点也没有写$

首先容易想到要是让前面的S尽可能多就好了

$所以直接按照S在字符串中所占的比重从小到大排序$

#include <bits/stdc++.h> using namespace std; #define int long long int n; const int maxn=3e5+10; struct p{ int l,r,len; string s; double mi; }a[maxn]; bool com(p a,p b){ return a.mi>b.mi; } signed main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i].s; a[i].len=a[i].s.length(); for(int j=0;j<a[i].s.length();j++) { if(a[i].s[j]=='s') a[i].l++; else a[i].r++; } a[i].mi=a[i].l*1.0/(double)a[i].len; } sort(a+1,a+1+n,com); int ans=0,q=0,w=0; for(int i=1;i<=n;i++) for(int j=0;j<a[i].len;j++) { if(a[i].s[j]=='s') q++; else w++,ans+=q; } cout<<ans; }