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;
}
真思路自然要大一点:(不会堆的这边请,一个大佬的:神奇传送门)
用一个大根堆维护左括号,小根堆维护右括号,遇上右括号就将大根堆堆顶弹出,如果大根堆空了,就加小根堆。如果小根堆空了就加大根堆,保证最后的一定小。
亲爱的代码同学又回来了:
#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;
}
完结撒花!!!