3848930_ac_922ms_596k.cpp

北大大牛代码 1240道题的原代码 超级权威

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

using namespace std;

struct node
{
	int id, n;
	bool operator < (const node &t)	const
	{
		return n > t.n;
	}
}num[50001];

int n, k;

bool check(int length)
{
	int i, ans = 0;

	for (i = 1; i <= k; i++)
	{
		if (num[i].n < length)
			break;
		ans += num[i].n / length;
		if (ans >= n)
			return true;
	}
	return false;
}

int main()
{
	int i, j;

	scanf("%d%d", &n, &k);
	for (i = 1; i <= k; i++)
	{
		scanf("%d", &num[i].n);
		num[i].id = i;
	}
	sort(&num[1], &num[1] + k);
	int min, max, mid;
	min = 1;max = n;
	int ans = -1;
	while (min <= max)
	{
		mid = (min + max) >> 1;
		if (check(mid))
		{
			ans = mid;
			min = mid + 1;
		}
		else
			max = mid - 1;
	}
	printf("%d\n", ans);
	for (i = 1; i <= k && n != 0; i++)
	{
		int t = num[i].n / ans;
		for (j = 0; j < t && n != 0; j++, n--)
		{
			printf("%d\n", num[i].id);
		}
	}
	return 0;
}