pku2614.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <algorithm>
using namespace std;
#define size 100000000
typedef struct 
{
	int s, e;
} Node;

Node nd[size];
int cnt, end;
int A, n;
int s, e, found;

bool cp(Node a, Node b)
{
	return a.s < b.s;
}

int Max(int x, int y)
{
	return x > y ? x : y;
}

void Merge()
{
	int i, j;
	for (i = 0, j = 0; j < end; j++)
	{
		if (nd[i].e >= nd[j].s)
		{
			nd[i].e = Max(nd[i].e, nd[j].e);
		}
		else
		{
			i++;
			nd[i] = nd[j];
		}
	}
	cnt = i + 1;
}

void Add()
{
	int i, j;
	end = cnt;
	
	for (i = 0; i < cnt; i++)
	{
		for (j = 1; nd[i]. e + (j - 1) * e <= A; j++)
		{
			nd[end].s = nd[i].s + j * s;
			nd[end].e = nd[i].e + j * e;
			end++;
		}
	}
	sort(nd, nd + end, cp);
	Merge();
}

int main()
{
	int i, k;
	while (scanf("%d %d", &A, &n) != -1)
	{
		A *= 1000;
		cnt = 1;
		nd[0].s = 0;
		nd[0].e = 0;
		found = 0;
		while (n--)
		{
			scanf("%d %d", &s, &e);
			k = e / (e - s) + 1;
			if (s * k <= A)
			{
				found = 1;
			}
			if (found)
			{
				continue;
			}
			Add();
		}
		for (i = 0; i < cnt; i++)
		{
			if (nd[i].e >= A)
			{
				break;
			}
		}
		if (found || nd[i].s <= A)
		{
			printf("0\n");
		}
		else
		{
			printf("%d\n", A - nd[i - 1].e);
		}
	}
	return 0;
}