2735601_wa.cc

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

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

using namespace std;

int n, D, xp;
struct node 
{
	int a, b;
	int s;
}inf[11];

int main()
{
	int i;
	int p[11], ans[11];
	double P, t;

	scanf("%d%d",&n,&D);
	for (i = 0; i < n; i++)
		scanf("%d%d%d",&inf[i].a,&inf[i].b,&inf[i].s);
	for (i = 0; i < n; i++)
		ans[i] = p[i] = i;
	P = -1;
	do 
	{
		t = 1;xp = D;
		for (i = 0; i < n; i++)
		{
			if (inf[p[i]].b<=xp)
				xp += inf[p[i]].s;
			else
				if (inf[p[i]].a>xp)
				{
					t = 0;
					break;
				}
				else
				{
					t *= (xp-inf[p[i]].a)/(inf[p[i]].b-inf[p[i]].a);
					xp += inf[p[i]].s;
				}
		}
		if (t > P)
		{
			P = t;
			for (i = 0; i < n; i++)
				ans[i] = p[i];
		}
	} while(next_permutation(p,p+n));
	printf("%.3lf\n",P);
	for (i = 0; i < n; i++)
		printf("%d ",ans[i]+1);
	printf("\n");
	return 0;
}