Codeforces Round #248 (Div. 1)——Ryouko's Memory Note

题目连接

  • 题意:

    给n和m,一行m个1<=x<=n的数。记c=Codeforces Round #248 (Div. 1)——Ryouko&#39;s Memory Note.如今仅仅能选择一个数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;
}

上一篇:java随机生成验证码


下一篇:mobile_音悦台