构造&贪心题单练习 | LOV3のbolg

构造+贪心(R1000)

剩余24h

# 有n个地点，每来往i，j两个地点就花费（i+j）mod（n+1），问遍历所有地点的最低花费
# 当i+j==n+1每两地花费最小，如1, n; 2，n-1
# 只需以1->n->2->n-1->3...这样的顺序花费就最小
n = int(input())

res = 0
# res = (n-1)/2
if n & 1: # n is odd
    res = (n - 1) >> 1
else:
    res = (n >> 1) - 1

print(res)

by: 易如鱼 & aYi_7 & 张少锋
分析：由于花费是要（i+j）mod（n+1），则尽可能使每段路程的i+j都接近n+1，通过样例中n=10的情况，不难发现解法。从1到n，花费为0(11%11 = 0)；从n走到2，花费为1(12%11=1)；从2到n-1，花费为0；从n-1到3，花费为1;从3到n-2…这样循环往复，每次向右走花费为零，向左走花费为1。据此不难写出通项公式：cost =（n-1）mod 2。

#include<cstdio>
int main()
{
	int n; scanf("%d",&n);
	printf("%d\n",(n-1)/2);
	return 0;
}