题目链接：http://codeforces.com/contest/805/problem/C

题意：n个数，从i到j的花费为(i+j)%(n+1)，问n个数都要走一遍，求最小花费。

希望尽可能地让i+j是n+1的倍数，所以构造：从1开始，那么下一个点必为n，因为(1+n)%(1+n)=0为最小花费，从n则可以到2，没办法，只能花费1。以此类推反复横跳。

1 #include 
     
       2 using namespace std; 3  4 const int maxn = 100100; 5 int n, a[maxn]; 6 bool vis[maxn]; 7  8 int main() { 9     // freopen("in", "r", stdin);10     while(~scanf("%d", &n)) {11         memset(vis, 0, sizeof(vis));12         int mod = n + 1;13         int ret = 0, cnt = 1;14         int cur = 1;15         int lo = 2;16         vis[cur] = 1;17         while(cnt <= n) {18             if(!vis[mod-cur]) {19                 vis[mod-cur] = 1;20                 cur = mod - cur;21             }22             else {23                 vis[lo] = 1;24                 cur = lo;25                 lo++;26                 ret++;27             }28             cnt++;29         }30         printf("%d\n", ret-1);31     }32     return 0;33 }
     

 

？？？找规律发现，这答案直接输出(n-1)/2就行了。。

1 #include 
     
       2 using namespace std; 3  4 const int maxn = 100100; 5 int n, a[maxn]; 6 bool vis[maxn]; 7  8 int main() { 9     // freopen("in", "r", stdin);10     while(~scanf("%d", &n)) {11         printf("%d\n", (n-1)/2);12     }13     return 0;14 }