3285569_ac_1438ms_696k.cc

来自「北大大牛代码 1240道题的原代码 超级权威」· CC 代码 · 共 50 行

#include <stdio.h>
#include <algorithm>

using namespace std;

int h[100001];
char packed[100001];

bool cmp(int a,int b)
{
	return a > b;
}

int main()
{
	int n, i, j, l, t, ans;

	scanf("%d%d",&n,&l);
	for(i = 0; i < n; i++)
	{
		packed[i] = '0';
		scanf("%d",&h[i]);
	}
	sort(h,h+n,cmp);
	ans = 0;
	for(i = 0; i < n; i++)
	{
		if(packed[i]=='1')
			continue;
		packed[i] = '1';
		ans++;
		j = n-1;
		t = l-h[i];
		while(j>i)
		{
			if(h[j]>t)
				break;
			if(packed[j]=='1')
			{
				j--;
				continue;
			}
			packed[j] = '1';
			break;
		}
	}

	printf("%d\n",ans);
	return 0;
}