首页 > 代码库 > Codeforces Round #248 (Div. 1)——Ryouko's Memory Note
Codeforces Round #248 (Div. 1)——Ryouko's Memory Note
题目连接
- 题意:
给n和m,一行m个1<=x<=n的数。记c=.现在只能选择一个数x变成y,序列中所有等于x的值都变成y,求最小的c - 分析:
对于一个数x,把与他相邻的所有的非x的数全部写下来。如果x增大,那么一部分值增大,一部分减小,且每个数的增大值或减小值都是x的变化值(均相等),也就是说总的结果只和比x大的数与比x小的数的数量有关,所以即中位数。
const int maxn = 110000; LL ipt[maxn]; map<LL, vector<LL> > mp; map<LL, vector<LL> >::iterator it; int main() { int n, m; while (~RII(n, m)) { mp.clear(); REP(i, m) { cin >> ipt[i]; } REP(i, m) { if (i > 0 && ipt[i - 1] != ipt[i]) mp[ipt[i]].push_back(ipt[i - 1]); if (i < m - 1 && ipt[i + 1] != ipt[i]) mp[ipt[i]].push_back(ipt[i + 1]); } LL ans = 0; FC(it, mp) { vector<LL>& ipt = it->second; sort(all(ipt)); LL t = 0, m = ipt[(LL)ipt.size() / 2]; REP(i, ipt.size()) { t += abs((it->first) - ipt[i]) - abs(m - ipt[i]); } ans = max(ans, t); } ans *= -1; REP(i, m - 1) ans += abs(ipt[i] - ipt[i + 1]); cout << ans << endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。