普及C组第三题（8.10）_C

概述2301. 【普及组T3或T4】线索 (File IO): input:assassin.in output:assassin.out 时间限制: 1000 ms 空间限制: 262144 KB 题目描述（为毛是图片）输入（为毛是图片）输出（为毛是图片）样例输入/输出（为毛是图片）数据范围限制（为毛是图片）思路：（1）伪思路当然要小一点：暴力模拟左右两边判断，能像多少种情况就打多少 2301. 【普及组T3或T4】线索
(file IO): input:assassin.in output:assassin.out 时间限制: 1000 ms 空间限制: 262144 KB 题目描述（为毛是图片）

输入（为毛是图片）

输出（为毛是图片）

样例输入/输出（为毛是图片）

数据范围限制（为毛是图片）

思路：

（1）伪思路当然要小一点：暴力模拟左右两边判断，能像多少种情况就打多少种。。。hhh。

小代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,p=0,q=0,ans=0,sum=0;
bool flag1[1000001],flag2[1000001];
struct assassin
{
int left1,right1,money;
char a;
};
assassin ezio[1000001];
bool cmp1(assassin x,assassin y)
{
return x.left1<y.left1;
}
bool cmp2(assassin x,assassin y)
{
return x.right1<y.right1;
}
int main()
{
memset(flag1,true,sizeof(flag1));
memset(flag2,sizeof(flag2));
cin>>n;
for(int i=1;i<=n;i++)
cin>>ezio[i].a;
for(int i=1;i<=n;i++)
{
cin>>ezio[i].money;
sum=sum+ezio[i].money;
}
for(int i=1;i<=n;i++)
{
if(ezio[i].a==‘(‘&&i!=n)
{
for(int j=i+1;j<=n;j++)
{
if(ezio[j].a==‘)‘&&flag2[j]==true)
{
p++;
ezio[p].right1=ezio[j].money;
flag2[j]=false;
}

}
}
else if(ezio[i].a==‘(‘&&i==n)
ans+=ezio[i].money;
if(ezio[i].a==‘)‘&&i!=1)
{
for(int j=i-1;j>=1;j--)
{
if(ezio[j].a==‘(‘&&flag1[j]==true)
{
q++;
ezio[q].left1=ezio[j].money;
flag1[j]=false;
}
}
}
else if(i==1&&ezio[i].a==‘)‘)
ans+=ezio[i].money;
}
cout<<q<<" "<<p<<endl;
sort(ezio+1,ezio+p+1,cmp1);
sort(ezio+1,ezio+q+1,cmp2);
for(int k=1;k<=p;k++)
cout<<ezio[k].left1<<" ";
for(int k=1;k<=q;k++)
cout<<ezio[k].right1<<" ";
for(int i=1;i<=n;i++)
{
if(p==0&&q==0)
break;
if(q>p)
{
ans=ezio[i].left1+ans;
q--;
}
else
if(p>q)
{
ans=ezio[i].right1+ans;
p--;
}
else
break;
}
if(p==0&&q==0)
cout<<sum;
else
cout<<ans;
}

真思路自然要大一点：（不会堆的这边请，一个大佬的：神奇传送门）

用一个大根堆维护左括号，小根堆维护右括号，遇上右括号就将大根堆堆顶d出，如果大根堆空了，就加小根堆。如果小根堆空了就加大根堆，保证最后的一定小。

亲爱的代码同学又回来了：

#include<iostream>#include<queue>using namespace std;int n,ans=0;char a[100001];int b[100001];priority_queue<int> q;priority_queue<int,vector<int>,greater<int> >p;int main(){    cin>>n;    for(int i=1;i<=n;i++)    cin>>a[i];    for(int i=1;i<=n;i++)    cin>>b[i];    for(int i=1;i<=n;i++)    {        if(a[i]==‘(‘)        q.push(b[i]);        else        {            p.push(b[i]);            if(q.empty())            {                ans+=p.top();                p.pop();            }            else            q.pop();        }    }    while(q.empty()==false)    {        ans+=q.top();        q.pop();    }    cout<<ans;}