《摆渡车》题解和反思

题目
这是一道看似很难的题目，但是打开思路，跳出dp这个思想枷锁，我们把这个题目当做一个实际问题去处理，其实用枚举的思想也能得到很好的分数，并且也很容易想到。

文章目录

• • 反思
  • 50分题解
  • 100分题解

反思

首先得去反思自己到底是什么原因在去年题目刚出来的时候没有做出来。是信念，有很笨的想法，内心自我否定，导致不敢去尝试。是决定。代码一遍写出来大都有各种数据区间没有卡好，这就需要耐心的一点点的调试。

50分题解

有一个不争的事实，每一个乘客的等车时间不会超过m。因为如果一个乘客的等车时间超过了m，那么完全可以在等待的时间内再发一个车去接它，而且不会影响后序的乘客等车。（不知道这算不算无后效性）用一个词语就是，并不会“牵一发动全身”。

30分思路：
用到比较笨的办法，枚举所有可能的发车时间，当所有人都接走了，那么比较下最小的等待时间。

例如从11这个时间开始，既可以从11发车，也可以从12发车，还可以从13发车…最后能从11+m发车。
如果第一次发车是11的话，那么下一班车的发车时间只能是大于等于11+m 。那么这班车的发车时间小于什么呢？我们可以猜测是11+m再加上m。
注意我们不考虑乘客的等车时间，我们是闭着眼睛去“瞎鸡儿”发车，如果这个乘客能上，它就上。佛系。也就是上一次的发车时间到这次的发车时间如果有乘客在傻傻的等待，那么就接上它去远方。
把上面的东西用代码描述如下：

#include 
#define UP(i,x,y) for(int i=x; i<=y; i++)
#define LEN 1000001
using namespace std;int top = 0; // timers数组最后元素为top-1
int ans = 0; 
int n; 
int m; 
int timers[LEN] = {0}; // 第i个乘客的等待时间 （已经去重）
int arr[LEN] = {0};
int num[LEN] = {0}; // 在第t时间等待的乘客有几位
vector<int> fas;
int minVal = 9999999;// return 时间t之后（不包括t），第一个等车的人的编号 
int getNextCus(int t)
{int cusWaitTime = 0; // 等车人的时间 while(t++){if(num[t] != 0){cusWaitTime = t;break;}if(t >= timers[top-1]){return -1;}	} // 寻找等车人的编号 for(int i=0; i<top; i++){if(timers[i] == cusWaitTime){return i;}}
} // 时间a~b包含ab，区间内有没有乘客   1：有乘客    0：没有乘客 
int isHaveCus(int a, int b)
{for(int i = a; i<=b; i++){if(num[i] != 0){return 1;}}return 0;
}/* ar: 上一次车子到达时间*/
void dfs(int ar) 
{// 上一次的发车时间大于最大等待者，那么最后乘客肯定上车了 // 那么回溯if(ar - m >= timers[top - 1]){minVal = min(ans, minVal); return ;}// 枚举这次可以发车的时间for(int fa = ar; fa <= ar + m; fa++){// 从上次发车到这次发车，这段时间里面所有等车的人的总等待时间int rec = 0;for(int i=0; i<top; i++){if(timers[i] > ar-m and timers[i] <= fa){rec += (fa - timers[i]) * num[timers[i]]; // 等待的时间 }}ans += rec;dfs(fa + m);ans -= rec;} 
}int main(){int t = 0;cin>>n>>m

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！