CF - 805C. Find Amir - 贪心思维+构造

1.题目描述：

C. Find Amir time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

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  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.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the number of schools.

Output

Print single integer: the minimum cost of tickets needed to visit all schools.

Examples input 2 output 0 input 10 output 4 Note

In the first example we can buy a ticket between the schools that costs .

2.题意概述：

旅行商问题，旅行商从1点出发，其中从i点到j点的花费是(i + j) mod (n + 1)，求遍历所有点的最小花费。

3.解题思路：

很容易想到贪心地走i + j = n + 1 这个点，再仔细列出来发现例如n = 10，那么最优的走法是1->10->2->9->3->8->4->7->5->6，再看奇数例如5走法是1->5->2->4->3

很容易发现，对cost贡献来源于从第二个数开始到最中间那个数的次数，

那么答案就出来了，如果是奇数贡献就是n/2，偶数就是n/2-1。

4.AC代码：

#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define maxn 100100 #define lson root << 1 #define rson root << 1 | 1 #define lent (t[root].r - t[root].l + 1) #define lenl (t[lson].r - t[lson].l + 1) #define lenr (t[rson].r - t[rson].l + 1) #define N 1111 #define eps 1e-6 #define pi acos(-1.0) #define e exp(1.0) using namespace std; const int mod = 1e9 + 7; typedef long long ll; typedef unsigned long long ull; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); long _begin_time = clock(); #endif int n; while (~scanf("%d", &n)) { if (n == 1) puts("0"); else { if (n & 1) printf("%d\n", n / 2); else printf("%d\n", n / 2 - 1); } } #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms.", _end_time - _begin_time); #endif return 0; }