HDU 5935 Car 倒序增数组

399人浏览 / 1人评论

题目链接

  • Car
    • 这一题我做了很长时间,考虑了很多情况。思维题的难度应该属于比既定算法和数据结构还要捉摸不定。
    • 我们需要让车子的速度不断递增,又需要总时间最小。
    • 首先,容易想到差分,预处理出每一段的距离:diff[0]=a[0], diff[i]=a[i]-a[i-1]
    • 这样一来我们就得到每一段的距离,贪心思想希望每一段时间越少越好,最极端的情况就是1。但是若第一段为1,则后面不可以有小于第一段长度的段出现(否则那一段的时间将小于1,不合题意),所以我们想到一种贪心,就是预先处理好所有段右边(包括本身)最小的段长度值,保存在suffix数组中。suffix[i]=min(diff[i], diff[i+1], diff[i+2], ..., diff[n-1])
    • 处理好suffix数组,我们就可以贪心地让所有的段i的时间(存在time数组中)都取刚好≥suffix[i]的最小整数。
    • 但是新的问题出现了,我们只是保证了这一段的速度小于后面最小的一段的速度,可是后面还有次小段速度、第三小段速度……我们并没有考虑完全,如何修正这一模型就是当务之急。
    • 我们发现按照刚才的方法,最后一段的时间和倒数第二段的时间一定是最优且正确的,且倒数第三段正确的可能性非常高,以此类推。
    • 我们可以从后向前修正刚刚得到的值,如果一个段和它后面那一段diff[i]*time[i+1]>diff[i+1]*time[i](即diff[i]/time[i]>diff[i+1]/time[i+1],v[i]>v[i+1]),那么它就是不正确的,我们需要将它的速度修改为刚好≤v[i+1]的一个数,即time[i]=ceil(diff[i]*times[i+1]/diff[i+1])。
    • (suffix数组完全不必要,这里说的是思考这一题时的一些思路,实际代码直接从后向前增数组即可)
    • 注意:不要使用浮点数,遇到分母需要乘到另一边去。ACM题目能不用浮点数就不用浮点数。

代码:

#include<cstdio>
#include<algorithm>
using namespace std;
int a[(int)1e5+10],diff[(int)1e5+10],suffix[(int)1e5+10],times[(int)1e5+10];
int main()
{
	int T,kcase=0;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		scanf("%d",&n);
		for(int i=0;i<n;++i)
		{
			scanf("%d",&a[i]);
		}
		diff[0]=a[0];
		for(int i=1;i<n;++i)
		{
			diff[i]=a[i]-a[i-1];
		}
		suffix[n-1]=diff[n-1];
		for(int i=n-2;i>=0;--i)
		{
			suffix[i]=min(suffix[i+1],diff[i]);
		}
		long long total=0;
		for(int i=0;i<n;++i)
		{
			times[i]=diff[i]/suffix[i];
			if(diff[i]%suffix[i])
			{
				++times[i];
			}
		}
		for(int i=n-2;i>=0;--i)
		{
			if(diff[i]*(long long)times[i+1]>diff[i+1]*(long long)times[i])
			{
				if(diff[i]*(long long)times[i+1]%diff[i+1])
				{
					times[i]=diff[i]*(long long)times[i+1]/diff[i+1]+1;
				}
				else
				{
					times[i]=diff[i]*(long long)times[i+1]/diff[i+1];
				}
			}
		}
		for(int i=0;i<n;++i)
		{
			total+=times[i];
		}
		printf("Case #%d: %lld\n",++kcase,total);
	}
	return 0;
}

全部评论