Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

贪心+树状数组

Posted by 322019281 at 2018-12-31 11:01:52 on Problem 1201
#include<cstdio>
using namespace std;

const int N=50001;
int a[N],b[N],c[N],t[N+1];
bool v[N+1];

void qsort(int l,int r)
{
	int i=l,j=r,k=b[l+r>>1],tmp;
	while(i<=j)
	{
		while(b[i]<k)i++;
		while(b[j]>k)j--;
		if(i<=j)
		{
			tmp=a[i];
			a[i]=a[j];
			a[j]=tmp;
			tmp=b[i];
			b[i]=b[j];
			b[j]=tmp;
			tmp=c[i];
			c[i]=c[j];
			c[j]=tmp;
			i++;
			j--;
		}
	}
	if(i<r)qsort(i,r);
	if(l<j)qsort(l,j);
}

int sum(int x)
{
	int res=0;
	while(x)
	{
		res+=t[x];
		x-=x&-x;
	}
	return res;
}

void add(int x)
{
	while(x<=N)
	{
		t[x]++;
		x+=x&-x;
	}
}

int main()
{
	int n,i,j,tmp;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
		b[i]++;
	}
	qsort(1,n);
	for(i=1;i<=n;i++)
	{
		tmp=c[i]-(sum(b[i])-sum(a[i]));
		j=b[i];
		while(tmp>0)
		{
			while(v[j])j--;
			v[j]=true;
			add(j);
			tmp--;
		}
	}
	printf("%d\n",sum(N));
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator