sro蒟蒻求救,写了一下午的代码还是全WA,,QwQ,火火火火orz
查看原帖
sro蒟蒻求救,写了一下午的代码还是全WA,,QwQ,火火火火orz
363495
我爱杨帆楼主2020/8/11 17:27
#include<bits/stdc++.h>
using namespace std;
struct node
{
  char gender;
  int ability,difference,num;
  int nxt,pre;
 bool operator<(const node &X)const
 { if(difference!=X.difference)
   return difference>X.difference;
   else
   return num>X.num;}	
}s[2000000];
priority_queue<node >q;
int main()
{ int k,boys=0,girls=0;
  int n,t1,t2;
  cin>>n;
  for(int i=1;i<=n;i++)
   {
   cin>>s[i].gender;
   if(s[i].gender=='B') boys++;
   else girls++;
   s[i].num=i;
   s[i].nxt=i+1;
   s[i].pre=i-1;
   }
   s[1].pre=0;
   s[n].nxt=0;
   s[0].nxt=1;
   s[n+1].pre=n; 
  for(int i=1;i<=n;i++)
   cin>>s[i].ability;
  k=min(boys,girls);
  cout<<k<<endl; 
 for(int j=1;j<=k;j++) 
  {
  if(j==1)	
   {
   for(int i=s[1].nxt;s[i].nxt;i=s[i].nxt)
	if(s[i].gender!=s[s[i].pre].gender)
      {
		s[i].difference=abs(s[i].ability-s[s[i].pre].ability);
		q.push(s[i]);					 
	  }
   }
  else if(s[s[t2].pre].gender!=s[s[t1].nxt].gender&&s[s[t1].nxt].num&&s[s[t2].pre].num)
	   {
	   s[s[t1].nxt].difference=abs(s[s[t1].nxt].ability-s[s[t2].pre].ability);
	   q.push(s[s[t1].nxt]); 
       }
	  t1=q.top().num;
	  t2=s[q.top().num].pre;
	  q.pop(); 	      
	 while(!t1||!t2) 
	  {
	  t1=q.top().num;
	  t2=s[q.top().num].pre;
	  q.pop();
	  s[s[t2].pre].nxt=s[s[t1].nxt].num;
	  s[s[t1].nxt].pre=s[s[t2].pre].num;
      }
	s[s[t2].pre].nxt=s[s[t1].nxt].num;
	  s[s[t1].nxt].pre=s[s[t2].pre].num;
	cout<<t2<<" "<<t1<<endl;
  }			   		
}
2020/8/11 17:27
加载中...