蟻本少しずつ埋めます。
http://poj.org/problem?id=3104
POJ久しぶりにしたので注意点を。(POJ以外の注意点もあり)
- cout,cinはios::sync_with_stdio(false)にしても遅いのでprintf,scanfを使う。
- c++11は使えないのでtemplateらへんでcompile errorが生えるのを避ける。
- accumulateをdoubleで扱いたいなら第3引数を0.0にする。
ACされたコードを丸々載せておく。
#include <iostream> #include <cmath> #include <cstdio> #include <algorithm> #include <string> #include <vector> #include <queue> #include <string.h> #include <map> #include <fstream> #include <functional> #include <bitset> #include <stack> #include <set> #include <climits> #include <numeric> #include <complex> #define ADD(a, b) a = (a + (ll)b) % mod #define MUL(a, b) a = (a * (ll)b) % mod #define MAX(a, b) a = max(a, b) #define MIN(a, b) a = min(a, b) #define rep(i, a, b) for(int i = (a); i < (b); i++) #define rer(i, a, b) for(int i = (a) - 1; i >= (b); i--) #define all(a) (a).begin(), (a).end() #define sz(v) (int)(v).size() #define pb push_back #define sec second #define fst first #define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__) using namespace std; typedef long long ll; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef pair<int, pi> ppi; typedef vector<ll> vi; typedef complex<double> comp; void Debug() {cout << '\n'; } template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest) { cout << arg << " "; Debug(rest...); } template<class T>ostream& operator<< (ostream& out, const vector<T>& v) { out << "[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<< ", ";out<<v.back();}out << "]";return out;} template<class S, class T>ostream& operator<< (ostream& out, const pair<S, T>& v) { out << "(" << v.first << ", " << v.second << ")";return out;} const int MAX_N = 200010; const double eps = 1e-6; const ll mod = 1000000007; const int inf = 1 << 30; const ll linf = 1LL << 60; const double PI = 3.14159265358979323846; /////////////////////////////////////////////////////////////////////////////////////////////////// int N, C; ll A[MAX_N]; bool ok(ll m) { ll res = 0; rep(i, 0, N) { if(A[i] - m > 0) res += (A[i] - m + C - 1) / C; } if(res <= m) return true; else return false; } void solve() { scanf("%d", &N); rep(i, 0, N) scanf("%d", &A[i]); cin >> C; C--; if(C == 0) { ll mx = -1; rep(i, 0, N) MAX(mx, A[i]); printf("%lld\n", mx); } else { ll lb = -1, ub = (1LL << 60); while(ub - lb > 1) { ll m = (ub + lb) / 2; if(ok(m)) ub = m; else lb = m; } printf("%lld\n", ub); } } int main() { solve(); return 0; }