Tag Archives: 堆

舞蹈课 (C++堆的优先级与重载)

Posted on by

第三题：舞蹈课(dancingLessons)

时间限制：1秒

内存限制：256MB

输入：dancingLessons.in

输出：dancingLessons.out

问题描述

有n个人参加一个舞蹈课。每个人的舞蹈技术由整数来决定。在舞蹈课的开始，他们从左到右站成一排。当这一排中至少有一对相邻的异性时，舞蹈技术相差最小的那一对会出列并开始跳舞。如果相差最小的不止一对，那么最左边的那一对出列。一对异性出列之后，队伍中的空白按原顺序补上（即：若队伍为ABCD，那么BC出列之后队伍变为AD）。舞蹈技术相差最小即是的绝对值最小。

你的任务是，模拟以上过程，确定跳舞的配对及顺序。

输入

第一行为正整数：队伍中的人数。下一行包含n个字符B或者G，B代表男，G代表女。下一行为n个整数。所有信息按照从左到右的顺序给出。在50%的数据中，。

输出

第一行：出列的总对数k。接下来输出k行，每行是两个整数。按跳舞顺序输出，两个整数代表这一对舞伴的编号（按输入顺序从左往右1至n编号）。请先输出较小的整数，再输出较大的整数。

样例输入

4

BGBG

4 2 4 3

样例输出

2

3 4

1 2

样例输入

4

BGBB

1 1 2 3

样例输出

1

1 2

堆的操作

--堆默认为小根堆（重载Operator<） 小的放前面

注意此处用greater - 大根堆

#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (200000 + 10)
#define MAXAI (10000000 + 10)
int n;
char s[MAXN];
int a[MAXN];
bool b[MAXN];
struct pair2
{
	int x,y,w;
}ans[MAXN];

bool operator>(const pair2 a,const pair2 b)
{
	if (a.w==b.w) return a.x>b.x;
	return a.w>b.w;
}
void cout_pair(const pair2 a)
{
	printf("%d %dn",a.x,a.y);
}
priority_queue <pair2, vector<pair2>, greater<pair2> > q;
void push(int x,int y)
{
	pair2 now;
	now.x=x;
	now.y=y;
	now.w=abs(a[x]-a[y]);
	q.push(now);
//	cout<<"add "<<now.x<<' '<<now.y<<' '<<now.w<<'n';
}
int main()
{
	freopen("dancingLessons.in","r",stdin);
	freopen("dancingLessons.out","w",stdout);


	scanf("%dn%s",&n,s);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	memset(b,0,sizeof(b));
	for (int i=1;i<n;i++)
		if (s[i-1]!=s[i]) push(i,i+1);
	int tot=0;
	while (!q.empty())
	{
		pair2 now=q.top();
//		cout_pair(now);
		q.pop();
		if (b[now.x]||b[now.y]) continue;
		b[now.x]=1;
		b[now.y]=1;
		ans[++tot]=now;
		int l=now.x-1,r=now.y+1;
		if (l<1||r>n) continue;
		while (l>1&&b[l]) l--;
		while (r<n&&b[r]) r++;
		if (b[l]||b[r]) continue;
		if (s[l-1]!=s[r-1]) push(l,r);


	}

	printf("%dn",tot);
	for (int i=1;i<=tot;i++) cout_pair(ans[i]);

//	while (1);
	return 0;
}

RQNOJ 658(观光公交）

Posted on by

几大注意点：

1.一次使用氦气加速器会把后面分成好几段。

2.我们仅维护end[i],wait[i]恒定，因此需提前让wait[i]=max(wait[i-1],wait[i]);

3.w[i]+w[i+1]+...+w[j],且w恒定，故可预处理sum[i]（满足累加性）

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<functional>
#include<iostream>
#define MAXN 1000 +10
#define MAXM 10000 + 10
#define MAXK 100000 + 10
#define MAXD 100 + 10
#define MAXT 100000 + 10
using namespace std;
struct man
{
	int t,l,r;
}t[MAXM];
struct interval
{
	int l,r,w;
};

int n,m,k,ans,d[MAXN+1],wait[MAXN+1],w[MAXN+1],end[MAXN+1],sum[MAXN+1];
bool operator<(const interval a,const interval b)   //重载  operator < 的意思   为q做准备
{


	return a.w<b.w;
}

priority_queue<interval> q;   //priority_queue<Node, vector<Node>, greater<Node> >; 完整的不能用


void push(int l,int r)
{
	bool flag=0;
	for (int i=l;i<r;i++) if (d[i]) {flag=1;break;}
	if (!flag) return;
	int tot=sum[r]-sum[l];
	if (!tot) return ;
	interval now;
	now.w=tot;
	now.l=l;
	now.r=r;
	q.push(now);

//	 cout <<"add "<< now.l << ' ' << now.r <<' '<< now.w << endl;
}

int main()
{
//	freopen("qc.in","r",stdin);
	memset(wait,0,sizeof(wait));
	memset(w,0,sizeof(w));

	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=n-1;i++)
		scanf("%d",&d[i]);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&t[i].t,&t[i].l,&t[i].r);
		wait[t[i].l]=max(wait[t[i].l],t[i].t);
		w[t[i].r]++;
	}
	end[1]=0;
	for (int i=2;i<=n;i++)
	   end[i]=max(end[i-1],wait[i-1])+d[i-1];
	ans=0;
	for (int i=1;i<=m;i++)
	   ans+=end[t[i].r]-t[i].t;

	sum[1]=sum[0]=0;
	for (int i=2;i<=n;i++) {sum[i]=sum[i-1]+w[i]; wait[i]=max(wait[i-1],wait[i]);}

//	for (int i=0;i<=n;i++) cout<<end[i]<<' ';
//	cout<<endl;


	int tot=d[1],head=1;
	for (int i=2;i<=n;i++)
	{
		if (wait[i]>=end[i])
		{
			if (tot) push(head,i);
			tot=0;
			head=i;
		}
		tot+=d[i];
		/*
		tot+=w[i]*min(1,d[i]);
//		tot+=w[i];
		*/
	}


	if (tot) push(head,n);


//00	cout<<ans<<endl;
	//贪心
//	sort(t+1,t+m+1,cmp);

// 调试
/*   while( !q.empty() ){
        cout << q.top().l << ' ' << q.top().r <<' '<< q.top().w << endl;
        q.pop();
	}
*/
/*
	for (int i=1;i<=n;i++)
	{
		cout<<end[i]<<' ';
	}
*/
	while (k&&!q.empty())
	{
/*	cout<<"/////////"<<endl;
	for (int i=1;i<=n;i++)
	{
		cout<<end[i]<<' ';
	}
	cout<<endl;
	for (int i=1;i<=n;i++)
	{
		cout<<wait[i]<<' ';
	}

	cout<<endl;
*/
		interval now=q.top();
		q.pop();
		ans-=now.w;
		int i=now.l;
//000
//     cout << now.l << ' ' << now.r <<' '<< now.w << endl;
//      cout << ans << endl;
//000


		while (!d[i]) i++;
		d[i]--;
		int head=i,tot=0,i2=0;
		i++;
		while (i<=now.r/*&&wait[i]<end[i]*/)
		{
		//	tot+=w[i-1];
			end[i]--;
			//000
//		    for (int cse=1;cse<=n;cse++) cout<<end[cse]<<',';
//			cout<<endl;
			//-
//			cout<<i<<endl;
//			cout<<wait[i+1]<<' '<<end[i+1]<<endl;
			if (wait[i]==end[i])
			    {push(head,i);head=i;}
			i++;
		}

		i--;
		if (head!=now.r) push(head,now.r);

/*
		if (i>now.r) {cout<<"smile"<<endl;
			cout<<'<'<<' '<<i<<' '<<wait[i]<<' '<<end[i]<<' '<<endl;}
*/
//		cout<<"i2:"<<i2<<endl;
/*		if (i2) i=i2;
		i--;
		push(head,i);
		if (i<now.r)
		{
//			if (!d[head]) tot+=w[head];
			push(i,now.r);
		}
*/

		//处理 end[i] 显然最多影响到 now.r
		k--;
	}

	cout<<ans<<'n';


// 调试
/*
	    while( !q.empty() ){
        cout << q.top().l << ' ' << q.top().r <<' '<< q.top().w << endl;
        q.pop();
	}
	for (int i=1;i<=n;i++)
	{
		cout<<end[i]<<' ';
	}



*/


//	while (1);

}

POJ 2010(二叉堆-入门）

Posted on by

好像这题二分也可以做……

话说这年头写堆都不用Heapify 函数的？

Program P2010;
const
   maxc=100000;
   maxn=19999;
   maxaid=100000;
   maxf=2000000000;
type
   node=record
        a,b:longint;
        end;
   heap=record
        size:longint;
        d:array[1..maxc] of longint;
        end;
var
   n,c,f,i,j:longint;
   a:array[1..maxc] of node;
   h:heap;
   before,after:array[1..maxc] of longint;


procedure swap(var a,b:longint);
var
   p:longint;
begin
   p:=a;a:=b;b:=p;
end;
procedure qsort(l,r:longint);
var
   i,j:longint;
   m,p:node;
begin
   i:=l;
   j:=r;
   m:=a[(l+r) shr 1];
   repeat
      while a[i].a<m.a do inc(i);
      while a[j].a>m.a do dec(j);
      if i<=j then
      begin
         swap(a[i].a,a[j].a);
         swap(a[i].b,a[j].b);

         inc(i);dec(j);
      end;


   until i>j;

   if l<j then qsort(l,j);
   if i<r then qsort(i,r);


end;

procedure push(t:longint);
var
   i:longint;
begin
   with h do
   begin
      inc(size);
      d[size]:=t;
      i:=size;
      while i>1 do
      begin
         if d[i shr 1]>=d[i] then break;
         swap(d[i shr 1],d[i]);
         i:=i shr 1;
      end;
   end;
end;
procedure pop;
var
   i,j:longint;
begin
   with h do
   begin
      d[1]:=d[size];
      dec(size);
      i:=1;
      while i shl 1<=size do
      begin
         j:=i shl 1;
         if (j<size) then if d[j]<d[j+1] then inc(j);
         if d[j]<d[i] then break;
         swap(d[i],d[j]);
         i:=j;
      end;
   end;

end;
function front:longint;
begin
   exit(h.d[1]);
end;
function main:longint;
var
   i,j,mid,ans,num:longint;
begin
   mid:=n div 2;
   fillchar(before,sizeof(before),0);
   fillchar(after,sizeof(after),0);
   for i:=1 to mid do
   begin
      push(a[i].b);
      inc(before[mid+1],a[i].b);
   end;
   for i:=mid+2 to c-mid do
   begin
      if front<=a[i-1].b then before[i]:=before[i-1]
      else
      begin
         before[i]:=before[i-1]-front+a[i-1].b;
         pop;
         push(a[i-1].b);
      end;
   end;
   fillchar(h,sizeof(h),0);
   for i:=c downto c-mid+1 do
   begin
      push(a[i].b);
      inc(after[c-mid],a[i].b);
   end;
   for i:=c-mid-1 downto mid+1 do
   begin
      if front<=a[i+1].b then after[i]:=after[i+1]
      else
      begin
         after[i]:=after[i+1]-front+a[i+1].b;
         pop;
         push(a[i+1].b);
      end;
   end;
   ans:=f+1;
   num:=-1;
   for i:=mid+1 to c-mid do
      if f>=before[i]+after[i]+a[i].b then
      begin
         num:=i;
      end;
   if num=-1 then exit(-1);
   exit(a[num].a);
end;
begin
   while not seekeof do
   begin
      fillchar(h,sizeof(h),0);
      read(N,C,F);
      for i:=1 to c do read(a[i].a,a[i].b);
      qsort(1,c);
      writeln(main);

   end;
end.