POJ3232 Acclerator

Posted on | In |

有一个含有n辆车的车队，当前距离终点的距离已知，有m个加速器，每个加速器在一个时刻只能给一辆车用，一旦使用就会使得其速度由1变成k，加速器可以重复使用，问最快所有车辆到达终点的时间。

思路：二分枚举所需的最短时间。

对于1辆车要用num个加速器
num*k+(ans-num)>=a[i]

num>=(a[i)-ans)/(k-1)

限制条件

1.加速器最多使用次数ans*m;

2.对于每辆车而言单位时间内只能用一次加速器 所以num<=ans

3.题意 单位时间内只能有m个加速器，由1.2知条件3成立

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string.h>
typedef long long LL;
LL n,m,k,left,right;
LL a[100000];
using namespace std;
bool check(LL ans) {
	LL sum=ans*m;
	LL num;
	for(int i=0;i<n;i++){
		if(a[i]<=ans) num=0;
		else{
			if((a[i]-ans)%(k-1)==0)
			num=(a[i]-ans)/(k-1);
			else//注意整除不了的时候 还要用1个加速器 
			num=(a[i]-ans)/(k-1)+1;		
			if(num>ans) return false;	
			sum-=num;
			if(sum<0) return false;
			}
	}
	return true;
	
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
	cin>>n;
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	scanf("%d%d",&m,&k);
	LL maxn=-1;
	LL t=0;
	for(int i=0;i<n;i++)
	maxn=max(maxn,a[i]);
	if(k==1) {
		printf("%d\n",maxn);
		continue;//!!!
	}
	else{
	
	LL left=0,right=maxn;
	while(left<=right){
		LL mid=(left+right)/2;
		if(check(mid)) {
			t=mid;
			right=mid-1;
		}
		else left=mid+1;
	}
		printf("%d\n",t);
	}
}
}

开始一直Time Limit Exceeded
对比了网上的代码 发现逻辑基本差不多（https://www.cnblogs.com/fanminghui/p/3993539.html）

后来偶然看到https://blog.csdn.net/barry283049/article/details/42679317 把cin,cout全部替换后accepted！

time limited 可能的原因

  • 检查一下什么地方在什么数据下出现了死循环
  • 否则还是考虑换个思路解题的好。TLE除了死循环就是算法问题。