Loading... # 清北学堂noip2019-Day1 ## 贪心算法 > P.S. 每道题的代码我之后补加。。。 ### problem 1：Chocolate #### [Chocolate](https://www.luogu.org/problemnew/show/P3173) 一块$n\times m$的巧克力， 切成$n\times m$块。 巧克力上共有$n-1$条横线和$m-1$条竖线，每次沿着一条线将巧克力切开。 无论切割长短，横线切一次的代价是$y_1,y_2,y_3,...,y_{n-1}$，竖线是$x_1,x_2,x_3,...,x_{m-1}$。 求最小总代价。 $n,m\leq 10^5$ #### [题解](https://www.luogu.org/problemnew/solution/P3173) 横向切会使纵向次数+1，纵向同理。 所以肯定先切大的，再切小的。 于是把横纵放到一起排序，依次取最大值统计答案即可。 ---- ### problem 2 #### [USACO Allowance](https://www.luogu.org/problemnew/show/P2376) - John决定每个星期给b一点零花钱 - j有一些硬币， 共n种面额。每一个面额都能整除比他大的所有面额。 - 他想用给定的硬币集合（给出硬币种类及数量），每个星期至少给b某个零花钱的数目C。 - 请计算他最多能给多少星期零花钱。 #### [题解](https://www.luogu.org/problemnew/solution/P2376) - 阶段一：尽快接近C，用大面额的凑。 - 阶段二：超过C尽量少，用小面额的凑。 - 开始能用大面额就用大面额，直到凑到的$sum + a_i>C$，然后尽量用小的凑，直到$sum+a_i>C$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; int n, c; struct node{ int v, b; }a[30]; int k; int ans; bool cmp(const node &a, const node &b){ return a.v < b.v; } int main(){ scanf("%d%d", &n, &c); for(int i = 1; i <= n; i++){ int v, b; scanf("%d%d", &v, &b); if(v >= c) ans += b; else a[++k].v = v, a[k].b = b; } sort(a + 1, a + k + 1, cmp); printf("%d\n", ans); for(int i = 1; i <= k; i++){ printf("%d %d\n", a[i].v, a[i].b); } while(true){ int x = c; for(int i = k; i >= 1; i--){ while(a[i].b > 0 && x >= a[i].v){ x -= a[i].v; a[i].b--; } } if(x > 0){ for(int i = 1; i <= k; i++){ if(a[i].b > 0 && x <= a[i].v){ x -= a[i].v; a[i].b--; } } } if(x > 0) break; ans++; } printf("%d", ans); return 0; } ``` ---- ### problem 3 #### [Face the Right Way](https://www.luogu.org/problemnew/show/P2882) 给出一个长为n的F/B序列，n<=5000。 你可以每次选择连续长度为k的一段，进行FB转换。 使得最后整个序列全为F。 求最少的操作次数和对应的最小长度。 #### [题解](https://www.luogu.org/problemnew/solution/P2882?page=2) 因为同一个点翻转两次就与没有翻转的效果相同了，因此我们有一个贪心策略为： 左到右对于出现的每一个B翻转一次从当前点开始的区间，就能保证是最优解。 但是我们会发现这样是$n^2$的，再枚举长度，就变为了$n^3$。 因此，需要对区间翻转差分一下，总时间复杂度就是$n^2$的了。  然后下面是我的代码： ```cpp #include<bits/stdc++.h> using namespace std; int n, a[5009], dif[5009]; int mincnt = 0x3f3f3f3f, minlen; int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++){ char c; cin>>c; a[i] = (c == 'F'); } for(int len = 1; len <= n; len++){ int now = 0, cnt = 0; bool flag = true; for(int i = 1; i <= n; i++) dif[i] = 0; for(int i = 1; i <= n; i++){ now ^= dif[i]; if(!(a[i] ^ now)){ if(i + len - 1 > n){ flag = false; break; } now ^= 1; dif[i] ^= 1; dif[i + len] ^= 1; cnt++; } } if(flag){ if(cnt < mincnt){ minlen = len; mincnt = cnt; } } } printf("%d %d\n", minlen, mincnt); return 0; } ``` ---- ### problem 4 #### [旅行家的预算](https://www.luogu.org/problemnew/show/P1016) 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。 给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1,2,…,N）。 求最少的总费用，如果无法到达目的地，则输出“No Solution”。 #### [题解](https://www.luogu.org/problemnew/solution/P1016) 枚举途中经过的加油站，每经过一个加油站，计算一次花费 在一个加油站所需要加的油，就是能够支持它到达下一个油价比它低的加油站的量 如果在这个加油站即使加满油，都不能到达一个比它油价低的加油站，就把油箱加满，前往能够到达的加油站中油价最低的那个 如果在这个加油站即使加满油，都不能到达任意一个加油站，也不能到达终点城市，说明无解 ---- ### problem 5 #### [The Minima Game](https://www.luogu.org/problemnew/show/P3507) 给出N个正整数，AB两个人轮流取数，A先取。每次可以取任意多个数，直到N个数都被取走。每次获得的得分为取的数中的最小值，A和B的策略都是尽可能使得自己的得分减去对手的得分更大。在这样的情况下，最终A的得分减去B的得分为多少。 $n\leq 10^5$ #### [题解](https://www.luogu.org/problemnew/solution/P3507) - 身临其境的分析： 一方面要让自己取的数中的最小值尽量大， 一方面要让剩下数中的最大值尽量小。 故先手肯定会从大到小的取数， 并且取出的数是连续的一段。 - **证明：** 从大到小取数显然，若不是连续取数，则留下的数更多，大的数更多，会给对方更多的机会。所以必然是连续取数。 - 所以我们倒着来考虑一下，将所有的数从小到大排列之后，f[i]表示两人取完前i个数，先手减去后手的最大值。(这里先手后手是相对的，因为我们是倒序的，和实际取法是完全相反的，它实际上是处理出了1~i个数的情况下的最优解，A先从i开始往左边取，所以说考虑先手减后手最大值） ---- ### problem 6 #### [[ZJOI2005]午餐](https://www.luogu.org/problemnew/show/P2577) N人来到了食堂，每个人由自己的打饭时间和吃饭时间。 食堂有两个打饭窗口，我们要把所有的人分成两队，然后一号队伍到一号窗口去排队打饭，二号队伍到二号窗口。每个人打完饭后立刻开始吃。 现在给定了每个人的打饭时间和吃饭时间，要求安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。 两个窗口是并行操作互不影响的，要求输出最佳方案下所有人吃完饭的时刻。 #### [题解](https://www.luogu.org/problemnew/solution/P2577) 贪心的理解，如果所有人都要早点走 那么吃饭时间长的就先吃，吃饭时间短的就晚点吃 所以，按照吃饭时间排序 每个人吃完饭的时间之和前面所有人的打饭的时间和有关 $f[i][j][k]$表示当前做到第i个人，第一列，第二列前面的人的打饭时间之和分别为$j,k$，最后一个人吃完饭的最小时间. 但直接三维状态会炸？ 所以，状态是f[i][j]表示当前做到第i个人， 第一列队伍前面所有人打饭的时间和是j时最后一个人吃完饭的最小时间 如果把这个人放在第一列$f[i][j]=min(f[i][j],max(f[i−1][j−Get[i]],j+eat[i]))$ 另外把这个人放在第二列$f[i][j]=max(f[i−1][j],sum[i]−j+eat[i])$ ---- ### problem 7 #### Water Tanks 给你一棵树，k升水，p块钱，进行一次游戏。 在游戏进行前，可以在任意个节点上放置1升水（总数不超过k） 游戏进行若干轮，每轮游戏开放所有节点，可以选择若干个节点关闭，代价为该节点的水数量。然后所有未关闭节点的水流向它的父亲(不会连续移动)。 最后，根节点中的水会被取走，水的数量为该轮游戏的盈利。 求最大盈利-代价。 #### 题解 在放置水的选择上，应该尽量选择深度相邻的节点，即将所有节点按照深度排序后，所选择放水的节点应该是连续的一段。 考虑选择某段区间后，所需要花费的钱。 假设深度范围[l , r] ，某个深度的点为 a[i] ，则花费钱为sigma(a[i]*(r-i)) 用两个指针进行扫描即可。 Last modification：January 27, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏