苏州优化网站哪家好,工程交易信息网,能源建设投资有限公司网站,门户网站如何帮企业做宣传目录 一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解 一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
3666 -- Making the Grade (poj.org) 二、解题报告
1、思路分析
先不考虑…目录 一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解 一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
3666 -- Making the Grade (poj.org) 二、解题报告
1、思路分析
先不考虑题目的问题先明确一点给定一个整数序列a求一整数x使得Σ|a[i] - x|最小那么x为序列a中的中位数证明很简单类似于剥洋葱 对于本题而言要求得到非严格递增/递减的序列b使得Σ|ai - bi|最小
假设前k个数字已经得到b1~bk那么对于ak1如果ak1 ak那么我们直接取bk1 ak1
否则令bj ~ bk1取aj ~ ak1的中位数我们先不关心j如何取我们得出一个结论b序列都是a序列中的数
我们先将a升序/降序排列因为题目要求所以我们要升序降序各dp一次
定义状态f[i][j]为bi aj时的前i个差的绝对值之和的最小值
那么f[i][j] min(f[i - 1][j]) abs(a[i] - b[j]) 2、复杂度 时间复杂度 O(nlogn)空间复杂度O(n^2) 3、代码详解
#include iostream
#include cstring
#include cmath
#include algorithm
#include climits
using namespace std;
const int N 2005;
int n, a[N], b[N];
long long f[N][N], ans LLONG_MAX;
void solve()
{for (int i 1; i n; i)f[1][i] abs(a[1] - b[i]);for (int i 1; i n; i){long long mi LLONG_MAX;for (int j 1; j n; j)f[i][j] (mi min(mi, f[i - 1][j])) abs(a[i] - b[j]);}for (int i 1; i n; i)ans min(ans, f[n][i]);
}
int main()
{//freopen(in.txt, r, stdin);ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin n;for (int i 1; i n; i)cin a[i], b[i] a[i];sort(b 1, b n 1);solve();reverse(b 1, b n 1);solve();cout ans;return 0;
}
