Codeforces Round #542
Codeforces Round #542
A. Be Positive
题意
给定一个数组$a_1,a_2,…,a_n$,让你到一个数字,是的数组内的所有数字处以这个数字之后,数组内大于0的数字超过$\cfrac{n}{2}$的上界。
题解
由于没有要求整除,所以直接看负数多还是正数多,哪个超过上届,就用$-1或者1$
ac代码
1 |
|
B. Two Cakes
题意
两个人要买$n$层蛋糕,他们必须从$1$开始买到$n$,之后给定$2n$个蛋糕店,他们从$1$这个点出发,之后去买蛋糕。其中一旦一个人从一家蛋糕店买了蛋糕,那么另外一个人就不能在那家蛋糕店买蛋糕。问两个人花费的最少步数是多少?
题解
由于每一步只有两种可能,一个人去$x+1$中的一家蛋糕店,另外一个人去另一家。每一步的选择都只有两种,且无后效性。所以我们用贪心来解决。每一步的时候都选择花费步数最少的选择。
ac代码
1 |
|
C. Connect
题意
Alice要从一个陆地到另外一块陆地,需要建造一座大桥,问桥的花费要最少。
- 桥的花费是欧几里得距离的平方
- 只能建造一座桥
- 可能不需要建造桥
题解
由于只建造一座桥,所以我们可以枚举起始点的陆地和终点的陆地,之后挑选出最近的点。
由于数据小,随便做。
ac代码
1 |
|
D2. Toy Train
题意
Alice开火车,他火车的轨道是确定的,之后火车开的方向也是确定的,火车的轨迹是一个圈,轨迹上有很多站点,每个站点上有糖果。
- 火车在站点上只可以拿起一个糖果
- 火车在站点上可以放下无限个糖果
目标是将所有站点上的糖果放到指定的站点所花费的时间最小。
题解
由于每一个站点都是独立的。你只需要管他是怎么拿起来的。所以每一个站点如果有$x$个糖果,那么从他开始至少要$x-1$圈加上一个最短的距离。所以我们可以枚举每一个站点所需要的最远距离。
假设从$i$起始点到$j$站点。那么我们开始的距离是$dis(i,j)=(j-i+n)\mod n$。
之后我们需要$x-1$圈。$(x-1)\times n$
之后我们需要从那个点到最近的放置点.$dis(j,z) = (z-j+n)\mod n$
之后两层循环即可。
ac代码
1 |
|