題目大意：給定幾個(gè)片段進(jìn)行排序，使得結(jié)果中字符串“sh”出現(xiàn)次數(shù)最多（不需要連續(xù)），并輸出摄乒。
思路是抄的：
題意：給n個(gè)只包含‘s’和‘h’的字符串，調(diào)整他們的順序，使拼起來(lái)的串含有最多的以‘s’開(kāi)頭以‘h’結(jié)尾的字串馍佑。
思路：首先考慮子串?dāng)?shù)目的計(jì)算對(duì)于兩個(gè)字符串t1和t2斋否。對(duì)于每個(gè)給定的字符串，其內(nèi)部順序是不可以改變的拭荤，因此記錄它含有的s茵臭，h，和內(nèi)部sh字串的數(shù)目就已經(jīng)包含計(jì)算子串所需要的全部信息了舅世，不妨抽象為一個(gè)數(shù)據(jù)結(jié)構(gòu)
struct{
int cnts;//含有的s數(shù)量
int cnth;//含有的h數(shù)量
int ns;//內(nèi)部sh子串?dāng)?shù)量
};
1
2
3
4
5
容易計(jì)算出連接t1-t2形成的串有的子串?dāng)?shù)量為t1.ns + t2.ns + t1.cnts × t2.cnth旦委。在尋找最大子串?dāng)?shù)量的過(guò)程中，t1.ns 和 t2.ns無(wú)論怎么擺放都不變雏亚，調(diào)整順序只改變了用哪些字符串的cnts來(lái)乘哪些字符串的cnth缨硝，因此可以給這個(gè)數(shù)據(jù)結(jié)構(gòu)定義一個(gè)先后關(guān)系，如果t1.cnts × t2.cnth > t2.cnts × t1.cnth 罢低，那么就認(rèn)為t1應(yīng)該排在t2前面查辩，如果兩個(gè)乘積相同，就應(yīng)該把含‘s’更多的字符串放在前面网持。有了這個(gè)關(guān)系宜岛，就可以用sort函數(shù)來(lái)排序啦，最后的計(jì)算也比較容易翎碑，應(yīng)該注意到一點(diǎn)是谬返，s和h的數(shù)量可以達(dá)到幾萬(wàn)，相乘的結(jié)果用int保存可能會(huì)溢出日杈。
實(shí)際上，我一開(kāi)始的想法是差不多的佑刷，只不過(guò)有一個(gè)問(wèn)題莉擒，我一直糾結(jié)于會(huì)不會(huì)出現(xiàn) a>b b>c c>a ,這種矛盾的情況，仔細(xì)想想瘫絮，是不會(huì)的涨冀，這種情況出現(xiàn)的前提是有n相等的片段，但其實(shí)排序的時(shí)候麦萤，是對(duì)所有的元素遍歷鹿鳖，排在a后面的絕對(duì)不會(huì)比排在b后面的更優(yōu)秀（大概就這么個(gè)意思......）
#include <stdio.h>
#include<algorithm>
using std::sort;
struct sh
{
unsigned long cnts;
unsigned long cnth;
int ns;
sh():cnts(0),cnth(0),ns(0) {}
}str[100005];
bool cmp(sh a, sh b) {
unsigned long tempa = a.cnts*b.cnth;//用unsigned long 暫存結(jié)果
unsigned long tempb = a.cnth*b.cnts;
if (tempa >tempb)return true;
else if (tempa < tempb)return false;
else {//“相等”的情況
//把含's'更多的字符串放在前面，能與其他字符串生成更多的sh子串
if (a.cnts > b.cnts)
return true;
if (a.cnts < b.cnts)return false;
else {
return a.cnth < b.cnth;
}
}
}
char d;
int main() {
int n;
long long ans=0, ts=0, th=0;
scanf("%d", &n);
scanf("%c", &d);//額外的換行符
for (int i = 0; i < n;++i) {
while (1)
{
scanf("%c", &d);
if (d == 's')str[i].cnts++;
else if (d == 'h') { str[i].cnth++; str[i].ns += str[i].cnts; }
else break;//讀取到回車(chē)壮莹，一個(gè)輸入結(jié)束
}
}
sort(str, str + n, cmp);//按我們定義的先后關(guān)系排序
//最后的計(jì)算翅帜，用ts記錄當(dāng)前位置前面已經(jīng)有多少個(gè)s
for (int i = 0; i < n; ++i) {
//加上這個(gè)字符串的內(nèi)部sh子串?dāng)?shù)
ans += str[i].ns;
//這個(gè)字符串與前面的所有的字符串產(chǎn)生sh子串?dāng)?shù)
ans += ts*str[i].cnth;
//更新ts
ts += str[i].cnts;
}
printf("%I64d\n", ans);
}
1 結(jié)構(gòu)體數(shù)組的合理運(yùn)用以及初始化
2 cmp的自定義
3 各種情況的邏輯判斷
4 有時(shí)候看起來(lái)要分兩種情況的問(wèn)題可能可以并
