80pts 4# 9# WA
查看原帖
80pts 4# 9# WA
345930
Gold14526神金楼主2023/7/11 14:51
#include<bits/stdc++.h>
using namespace std;
int num;
char ch;
int read()
{
	num=0;
	ch=getchar();
	while(ch<'0'||ch>'9')
	{
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		num=(num<<1)+(num<<3)+ch-'0';
		ch=getchar();
	}
	return num;
}
short n,ans;
struct node{
	int tall,len;
}a[2001];
bool cmp(short x,short y)
{
	return a[x].tall>a[y].tall;
}
bool cmp2(node x,node y)
{
	return x.len+x.tall<y.len+y.tall;
}
struct priority_que{
	short a[2001];
	short t=0;
	short size(){return t;}
	short top(){return a[1];}
	void pop()
	{
		if(t==0)return;
		int x=1;
		a[1]=a[t];
		t--;
		while((x<<1)<=t)
		{
			if(cmp(a[x],a[(x<<1)])&&((x<<1|1)>t?1:cmp(a[x],a[(x<<1|1)])))break;
			if((x<<1|1)>t)
			{
				swap(a[x],a[(x<<1)]);
				x=(x<<1);
				continue;
			}
			else if(cmp(a[(x<<1)],a[(x<<1|1)]))
			{
				swap(a[x],a[(x<<1)]);
				x=(x<<1);
			}
			else
			{
				if(cmp(a[x],a[(x<<1|1)]))break;
				swap(a[x],a[(x<<1|1)]);
				x=(x<<1|1);
			}
		}
	}
	void push(short s)
	{
		a[++t]=s;
		int x=t;
		while(x>1&&!cmp(a[(x>>1)],a[x]))
		{
			swap(a[x],a[(x>>1)]);
			x=x>>1;
		}
	}
	bool empty(){return t==0;}
	void clear(){t=0;}
}q;
int tot,high;
int s[2001];
int main()
{
	//freopen("p4823.in","r",stdin);
	//freopen("p4823.out","w",stdout);
	n=read();
	for(short i=1;i<=n;++i)
	{
		a[i].tall=read();
		a[i].len=read();
	}
	sort(a+1,a+n+1,cmp2);
	high=read();
	s[n]=a[n].tall;
	for(short i=n-1;i>=1;--i)
	{
		s[i]=s[i+1]+a[i].tall;
	}
	for(short i=1;i<=n;++i)
	{
		if(tot+s[i]+a[i].len>=high)
		{
			q.push(i);
			++ans;
		}
		else
		{
			if(!q.empty()&&a[q.top()].tall>a[i].tall)
			{
				tot+=a[q.top()].tall;
				q.pop();
				q.push(a[i].tall);
			}
			else
			{
				tot+=a[i].tall;
			}
		}
	}
	cout<<ans;
	return 0;
}
2023/7/11 14:51
加载中...