POI2013 TAK-Taxis

wjh15101051's space

卧薪尝胆，厚积薄发。

POI2013 TAK-Taxis

Date: Tue Sep 25 15:13:36 CST 2018

In Category: NoCategory

Description：

一条线段有三个点， $0$ 为初始位置， $d$ 为出租车总部位置， $m$ 为家的位置，人要叫车，有 $n$ 辆车可以提供，每辆车有一个路程上限，并且都从车站出发，叫的车行驶之后不必须回到车站，问最少叫几辆车。

$1\leqslant n \leqslant 5\times 10^5$

Solution：

首先发现一定有一辆车从 $d$ 到 $m$ ，先找一个满足这个条件最小的，然后从大到小依次考虑每辆车即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

inline ll read()

{

	register ll res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

ll m,d;

int n;

#define MAXN 500010

ll a[MAXN];

bool used[MAXN];

int main()

{

	scanf("%lld%lld%d",&m,&d,&n);

	for(int i = 1;i <= n;++i)a[i] = read();

	sort(a + 1,a + 1 + n);

	memset(used,false,sizeof(used));

	bool found = false;

	ll l;

	for(int i = 1;i <= n;++i)

	{

		if(a[i] >= m - d)

		{

			l = a[i];

			used[i] = true;

			found = true;

			break;

		}

	}

	if(!found)

	{

		puts("0");

		return 0;

	}

	ll p = 0;

	int ans = 0;

	for(int i = n;i >= 1;--i)

	{

		if(used[i])continue;

		if(m - p + d - p <= l)break;

		ans++;

		if(a[i] <= (d - p))

		{

			puts("0");

			return 0;

		}

		p += a[i] - (d - p);

		if(p >= m)

		{

			--ans;

			break;

		}

	}

	if(m - p + d - p > l)puts("0");

	else cout << ans + 1 << endl;

	return 0;

}

In tag: 算法-贪心

wjh15101051