題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)長(zhǎng)度為 n 的括號(hào)序列，現(xiàn)在允許的操作是對(duì)于一段區(qū)間 [ l , r ] 內(nèi)的括號(hào)重新排列，所需要的花費(fèi)為區(qū)間長(zhǎng)度，問如果想要使得括號(hào)序列變?yōu)檎_的形式，最少花費(fèi)為多少

題目分析：括號(hào)的正常形式不用多啰嗦了吧，無非就是必須滿足全都匹配，無非法嵌套等等，比較簡(jiǎn)單的貪心，講一下如何貪心吧，O( n )掃一遍字符串，如果遇到了左括號(hào)，先保存起來，后續(xù)遇到了右括號(hào)時(shí)，如果前面已經(jīng)有了保存的左括號(hào)，那么可以抵消，則對(duì)答案沒有貢獻(xiàn)，但如果前面沒有保存的左括號(hào)時(shí)，說明這個(gè)位置開始，括號(hào)序列需要重新排序，那么我們貪心去找最靠近這個(gè)位置的左括號(hào)來和這個(gè)右括號(hào)匹配，找到后使整個(gè)區(qū)間重新排序就好了，至于找到的標(biāo)準(zhǔn)，就是左括號(hào)的數(shù)量等于右括號(hào)的數(shù)量，具體的看代碼也就能夠理解了，在進(jìn)行操作之前記得判斷一下 -1 ，也就是整個(gè)序列中左括號(hào)的數(shù)量與右括號(hào)的數(shù)量不相等

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;int n;char s[N];bool check() {int cnt1=0,cnt2=0;for(int i=0;i<n;i++)if(s[i]=='(')cnt1++;elsecnt2++;return cnt1==cnt2; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);scanf("%d%s",&n,s);if(!check())return 0*printf("-1");int ans=0;int l=0,r=0,mark=-1;//l:記錄左括號(hào)的數(shù)量,r:記錄右括號(hào)的數(shù)量,mark:記錄右括號(hào)需要重排時(shí)的首位置for(int i=0;i<n;i++){if(s[i]=='(')//如果是左括號(hào)，那么l++l++;if(s[i]==')')//如果是右括號(hào){if(l)//如果有左括號(hào)，那么直接抵消{l--;}else//否則記錄一下右括號(hào)現(xiàn)在有多少個(gè){r++;if(mark==-1)//如果是首次失配，記錄一下位置mark=i;}}if(l==r&&l)//如果當(dāng)前左括號(hào)的數(shù)量可以與右括號(hào)的數(shù)量匹配，則當(dāng)前區(qū)間可以重新排序了{(lán)ans+=i-mark+1;//記錄貢獻(xiàn)l=r=0;//初始化mark=-1;}}printf("%d\n",ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1323C Unusual Competitions(贪心)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。