保存されている過去のバージョンの一覧

Codeforces Round #592 DIV2 E問題 - Minimizing Difference

Source

Codeforces Round #592 DIV2 E問題 (2500pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20191027-1）のコード

C++に変換後のコードはこちら

//no-unlocked
int N, A[1d5]; ll K;
int sz, num[1d5], len[1d5];
{
  int res;
  ll mx;
  set< pair<int,int> > s;
  pair<int,int> x, y;

  rd(N,K,A(N));
  sortF(N,A);
  sz = runLength(N, A, num, len);
  rep(i,sz) s.insert( make_pair(num[i], len[i]) );
  for(;;){
    if(s.size()==1) break;
    x = getFirst(s);
    y = getLast(s);
    if(x.second <= y.second){
      x = popFirst(s);
      y = getFirst(s);
      mx = min(K / x.second, y.first - x.first);
      if(mx == 0) s.insert(x), break;
      x.first += mx;
      K -= mx * x.second;
      if(y.first == x.first){
        x.second += y.second;
        popFirst(s);
        s.insert(x);
      } else {
        s.insert(x);
      }
    } else {
      x = popLast(s);
      y = getLast(s);
      mx = min(K / x.second, x.first - y.first);
      if(mx == 0) s.insert(x), break;
      x.first -= mx;
      K -= mx * x.second;
      if(y.first == x.first){
        x.second += y.second;
        popLast(s);
        s.insert(x);
      } else {
        s.insert(x);
      }
    }
  }
  if(s.size()==1) wt(0), return 0;
  x = getFirst(s);
  y = getLast(s);
  res = y.first - x.first;
  wt(res);
}

Current time: 2024年04月23日19時30分57秒
Last modified: 2019年11月02日02時58分39秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF592 CF_Div2_E
トップページに戻る

Logged in as: unknown user (not login)