Codeforces Round #248 DIV1 A問題/DIV2 C問題 - Ryouko's Memory Note

Source

Codeforces Round #248 DIV1 A問題 (500pt)
Codeforces Round #248 DIV2 C問題 (1500pt)
Problem description

問題概要

$N$ ページから成るノートがある．
$M$ 回だけ順番に $A_1, A_2, \ldots, A_M$ のページを開きたい．
ここで，手間はページ間の移動距離の和
　　$\displaystyle \sum_{i=1}^{M-1} |A_i-A_{i+1}|$
とする．
ある $1$ ページの内容を別の $1$ ページに書き写して消しても良い．
つまり，$1$ 回だけ数列 $\{A_k\}_{k=1}^M$ にでてくる全ての $x$ を $y$ に変更できる．
この時，手間の和の最小値を求める問題．

解法

いくつ手間を削減できるかの最大値を求める．
各整数 $k$ について，自分と隣り合う異なる整数を全部列挙しておく．
隣も $k$ ならば，$k$ を変更した時一緒に変更されて，手間に貢献しないので無視する．
$k$ を変更するとしたら，列挙した整数の中の中央値に変更すると削減できる手間が最大となる．
なぜなら，$k$ を $1$ 増やした時に，$k$ より大きいものの数だけ手間が削減，$k$ より小さい物の数だけ手間が増加するので，大きい物も小さいものも同じ数だけあるような場所に落ち着くから．

C++のスパゲッティなコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

#define READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void writer(ll x, char c){int i,sz=0,m=0;char buf[20];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

vector<int> ni[100001];
int N, A[100001];

int main(){
  int i, j, k;
  ll res = 0, sa = 0;
  ll tmp, opt;

  reader(&N);
  reader(&N);
  rep(i,N) reader(A+i);
  REP(i,1,N) res += abs(A[i]-A[i-1]);

  REP(i,1,N) if(A[i-1]!=A[i]){
    ni[A[i-1]].push_back(A[i]);
    ni[A[i]].push_back(A[i-1]);
  }

 
  rep(i,100001) if(ni[i].size()){
    tmp = opt = 0;
    sort(ni[i].begin(), ni[i].end());
    
    rep(j,ni[i].size()) tmp += abs(i-ni[i][j]);

    k = ni[i][ni[i].size() / 2];
    rep(j,ni[i].size()) opt += abs(k-ni[i][j]);

    sa = max(sa, tmp-opt);
  }

  res -= sa;
  writer(res, '\n');

  myed;
  return 0;
}

Current time: 2024年04月25日22時02分50秒
Last modified: 2014年05月24日20時09分33秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF248 CF_Div1_A CF_Div2_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン：