AtCoder Regular Contest 105 B - MAX-=min

問題文について考えたこと

問題文へ

最大値と最小値が等しくなった時の値を求める問題と考えました。

最大値から最小値を引くので、最小値が更新される可能性に気を付けました。例えば、最大値5から最小値3を引いた場合などです。

手続きの２より、変更の際は同じ整数は一度に処理するため一つと考えてよく、C++のsetで最大値最小値を管理しました。

入力によっては、アウトだったろうと思います。

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
const double EPS = 1e-10;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = (1LL<<62) - (1LL<<31);
const ll MOD = 1000000007;


int main(void) {
  int N;
  cin >> N;
  set<ll> st;
  rep(i, N) {
    ll a;
    cin >> a;
    st.insert(a);
  }

  ll minv = *st.begin();
  ll maxv = *st.rbegin();
  while (minv != maxv) {
    ll num = maxv - minv;
    st.erase(maxv);
    st.insert(num);
    minv = *st.begin();
    maxv = *st.rbegin();
  }

  cout << minv << endl;
  
  return 0;
}