Codeforces Round #411 C. Find Amir

题意

A few years ago Sajjad left his school and register to another one due to security reasons. Now he wishes to find Amir, one of his schoolmates and good friends.

There are n schools numerated from 1 to n. One can travel between each pair of them, to do so, he needs to buy a ticket. The ticker between schools i and j costs (i+j) mod (n+1) and can be used multiple times. Help Sajjad to find the minimum cost he needs to pay for tickets to visit all schools. He can start and finish in any school.

任意选择起点和终点，要求遍历标号为 1 ~ n 的学校，从学校 i 到达学校 j 的花费为 (i+j)%(n+1) 。求遍历所有学校的最小费用。

解题思路

根据 (i+j) % (n+1) 可以得出：

1→n 费用为 0

2→n−1 费用为 0

3→n−2 费用为 0

因此，遵循下列路径的走法将是最小费用 1→n→2→n−1→... 。最小为 n−12

代码

#include<bits/stdc++.h> using namespace std; int main() { int n; scanf("%d",&n); printf("%d\n", (n-1)/2); }