传送门

题意

给出一个排列，定义\(value为\sum_{i=1}^{n-1}abs(f[i+1]-f[i])\)
\(swap(a[i],a[j])(i≠j)为一次交换\)，询问最少的交换次数使得value最大

分析

如果f[i+1]>f[i],答案就+f[i+1]-f[i];
如果f[i+1]<f[i],答案就+f[i]-f[i+1];
那么我们可以找到一个pretty good solution
定义 L 为 f[i]<=n/2, R 为 f[i]>n/2,
得到L R L R L R L R
或 R L R L R L R L
可以发现2~n-1的R加了2次，L减了2次，1和n加或减1次，那么必定是
将n/2和n/2+1放在（1和n）或（n和1）的位置

• If 2 is not first, bring it there
• If 3 is not the last, bring it there
• Swap every pair of 0 and 1 that are not on their positions

最新文章

1. Mybatis逆向工程构建项目实例.
2. I/O存取方式的形象比喻
3. (Unity)Unity自定义Debug日志文件，利用VS生成Dll文件并使用Dotfuscated进展混淆，避免被反编译
4. 远程方法调用（RMI）原理与示例
5. uname
6. http://blog.csdn.net/yaerfeng/article/details/27683813
7. Azure Bill
8. Codeforces Round #256 (Div. 2) 题解
9. 【京东详情页】——原生js爬坑之放大镜
10. 【视频编解码&#183;学习笔记】8. 熵编码算法：基本算法列举 &amp; 指数哥伦布编码
11. Kaggle竞赛 —— 房价预测 (House Prices)
12. xpath | 计算两个节点集
13. Installshield创建快捷方式不能正常运行的几种原因
14. Linux下pip使用国内源
15. Visual Studio 2017 以前的旧格式的 csproj Import 进来的 targets 文件有时不能正确计算属性（PropertyGroup）和集合（ItemGroup）
16. 复制CentOS虚拟机网络配置
17. springmvc找不到对应的requestmapping
18. java请求url返回json
19. shell编程——内部变量
20. 简易 PHP 教程小记

热门文章

1. 一根数据线玩转树莓派Zero
2. ngnix
3. css设置图片居中、居左、居右
4. [LeetCode][Java] Longest Common Prefix
5. 实现多线程的方式Runnable
6. INAPP
7. Vue生命周期方法。
8. OpenCV2.3.1在CentOS6.5下的安装
9. 文件管理中心iOS版简介
10. 使用 fetch 代替 ajax（在不支持的浏览器上使用 XHR）； This kind of functionality was previously achieved using XMLHttpRequest.