ABC081 D Non-decreasing 簡単なケースから考えてみたら解けた(・∀・)
ABC081 D Non-decreasing
問題概要
リンク参照
考察
- とりあえず適当なサンプルをいじる
- 分からん
- とりあえず全部正の数だとして考えると累積和とれば良いことに気が付く
- 全部負数の場合についても同様
- 問題は正負両方存在する場合→全部正 or 全部負数にしてしまえば累積和取って終了なことに気が付く
- 正数のmaxと負数の絶対値maxを比較して,大きいほうの符号に直してしまえばよい
- 自力ACなのはえらい(・∀・)
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> #define REP(i, n) for(int i = 0;i < n;i++) #define REPR(i, n) for(int i = n;i >= 0;i--) #define FOR(i, m, n) for(int i = m;i < n;i++) #define FORR(i, m, n) for(int i = m;i >= n;i--) #define SORT(v, n) sort(v, v+n); #define VSORT(v) sort(v.begin(), v.end()); #define llong long long #define pb(a) push_back(a) using namespace std; typedef long long int ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T, typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...)); } template<typename T, typename V> typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) { t = v; } template<typename T, typename V> typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) { for (auto& e : t) fill_v(e, v); } #define ARRAY_MAX 100005 const ll INF = 1e9; const ll MOD = 1e9 + 7; int dx[4] = { 1,0,0,-1 }; int dy[4] = { 0,1,-1,0 }; /******************************************************************************************/ ll sum[200005]; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; vector<int> a(n); int mini = 0; int mini_idx = 0; int maxi = 0; int maxi_idx = 0; for (int i = 0; i < n; i++) { cin >> a[i]; if (a[i] >= 0) { if (maxi < a[i]) { maxi = a[i]; maxi_idx = i + 1; } } else { if (mini > a[i]) { mini = a[i]; mini_idx = i + 1; } } } int cnt = 0; vector<pii> ans; if (abs(maxi) > abs(mini)) { cnt = maxi; //正にする for (int i = 0; i < n; i++) { if (a[i] < 0) { a[i] += cnt; ans.push_back(pii(maxi_idx, i + 1)); } } //累積和の感じ for (int i = 0; i < n - 1; i++) { ans.push_back(pii(i + 1, i + 2)); } } else { cnt = mini; //負にする for (int i = 0; i < n; i++) { if (a[i] > 0) { a[i] += cnt; ans.push_back(pii(mini_idx, i + 1)); } } for (int i = n - 1; i > 0; i--) { ans.push_back(pii(i + 1, i)); } } cout << ans.size() << endl; for (int i = 0; i < ans.size(); i++) { cout << ans[i].first << " " << ans[i].second << endl; } return 0; }