存在一条线段,有三个位置,
求最少需要多少辆出租车才能使 Byteasar 抵达目的地,无解输出
(建议您从上方链接进入我的个人网站查看此 Blog,在 Luogu 中图片会被墙掉,部分 Markdown 也会失效)
对于本题的思路和代码实现题解区的大佬们已经说的很详细了,这里主要对该题贪心策略中的一些细节进行论述与证明。
本来看这题面感觉很像一道 DP,然后口糊了半天也没想到什么优秀的状态和转移。。。
所以这道题是个贪心。
大概就是显然每辆车是需要先先走到人所在的位置然后向着总部走,这个过程我们可以考虑到显然优先选路程上限更大的车是更优的,这个很显然吧,如果选路程小的那么去掉前往人所在位置的路程,最终的贡献就会更小,会导致后面的车无用的路程更多,贡献也会变小。
但如果只考虑这样可能会导致因为前面为了解更优而耗费了过多的大车导致最终只剩下路程小于
然后贪心是正确的,但我的之前证明假了。。
update:
考虑对于最后一段
如果最后一辆车不能送到终点,那么在有解的情况下一定至少都再需要一辆大于
下面的内容均为之前写的假的证明,思路错了,这里留作纪念。
这时候仔细想一下就会发现一个问题,如果我们在到达总部之前的,乘坐的最后一辆车的行驶距离足够长,可以把我们送到超过总部
我们可以考虑令按照贪心策略预留的车距离为
显然如果
反之则为一般情况:
若
若
同时注意,上述我们论述的均为到达总部前最后一辆车能将我们送到超过总部的位置,如果最后一辆车无法将我们送达总部,我们也不能直接判定为无解,需要考虑到预留的那辆车也可以先向总部左侧行驶一段后再向右行驶到目的地,所以在跳出循环之后还需要判断一下。
因此在程序中我们除了判定是否满足到达
xxxxxxxxxx
741
2
3
4
5
6
7
8
9
10
11/******************************
12abbr
13
14******************************/
15
16using namespace std;
17using namespace __gnu_pbds;
18
19mt19937 rnd(random_device{}());
20int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
21bool rnddd(int x){return rndd(1, 100) <= x;}
22
23typedef unsigned int uint;
24typedef unsigned long long unll;
25typedef long long ll;
26typedef long double ld;
27
28
29
30template<typename T = int>
31inline T read(void);
32
33int M, D, N;
34vector < int > dis;
35
36signed main(){
37 // freopen("in.txt", "r", stdin);
38 M = read(), D = read(), N = read();
39 for(int i = 1; i <= N; ++i)dis.push_back(read());
40 sort(dis.begin(), dis.end(), greater < int >());
41 auto ptr = lower_bound(dis.rbegin(), dis.rend(), M - D);
42 if(ptr == dis.rend()){printf("0\n"); return 0;}
43 int val = *ptr;
44 dis.erase((++ptr).base());
45 int cur(0), ans(0);
46 for(auto i : dis){
47 cur += i - (D - cur);
48 ++ans;
49 if(cur <= 0){--ans; break;}
50 if(cur >= M){printf("%lld\n", ans); return 0;}
51 if(cur >= D - (val - (M - D)) / 2){printf("%lld\n", ans + 1); return 0;}
52 // printf("cur:%d, ans:%d\n", cur, ans);
53 }
54 if((D - cur) * 2 + (M - D) <= val)printf("%lld\n", ans + 1);
55 else printf("0\n");
56 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
57 return 0;
58}
59
60template<typename T>
61inline T read(void){
62 T ret(0);
63 short flag(1);
64 char c = getchar();
65 while(c != '-' && !isdigit(c))c = getchar();
66 if(c == '-')flag = -1, c = getchar();
67 while(isdigit(c)){
68 ret *= 10;
69 ret += int(c - '0');
70 c = getchar();
71 }
72 ret *= flag;
73 return ret;
74}
update-2022_09_XX 初稿
update-2022_10_08 修改了错误的贪心证明