二分探索の練習平均最小化小数の闇に注意割と平均最大（小）化好きかもしれない。 #include <bits/stdc++.h> using namespace std; struct edge{ int from; double time; int ren; }; const int INF = 1000000000; int n,m,c; double dp[10009]; bool flag[10006]; vector<edge> g</edge></bits/stdc++.h>…

問題文を読んで3秒で二分探索だと悟った。 こういう解法の決めつけはよくないと思うけど顕著すぎるんじゃ～ int n,m; int x[100003]; int y[100003]; bool ch(int d){ int co = 0; int h = x[0] + d; co++; for(int i = 1;i < m;i++){ if(x[i] > h){ co++; h…

頭が悪い。解法： priority_queueと、二分探索をもちいた。 おそらくJOI解説とほとんどおんなじ。 気が向いたら詳しく説明します。priority_queue、大きいほうからでてくるのすっかり忘れてましたね #include <cstdio> #include <utility> #include <queue> #include <vector> #include <algorithm> usin</algorithm></vector></queue></utility></cstdio>…

顕著な二分探索。なんかにぶたん使わなくても解けるらしいのですがややこしそうなので二分探索を使うほうがいいと思います。 #include <cstdio> #include <algorithm> using namespace std; int nau; int t[100003]; int main(){ while(1){ int d,n,m; scanf("%d",&d); if(d == </algorithm></cstdio>…

解法：半分全列挙 粘り勝ち。実際WA続いたのはAOJがサーバーの負担を減らすためにテストデータをまとめた結果初期化が必要になってそれを忘れていただけだからたぶん本番はﾀﾞｲｼﾞｮﾌﾞ。計算量はO(N^2logN).まあ典型のやつですね。蟻本を読もう。 #include <cstdio> #in</cstdio>…

二分探索・平均最大化。 日本TLE怖い協会 もうこの問題は解きたくない。 #include <cstdio> #include <algorithm> #include <functional> #include <utility> using namespace std; int n,k; int v[100010]; int w[100010]; pair<double, int> p[100012]; bool ans(double x){ for(int i = 0;i < n;i++){ p[i] = ma</double,></utility></functional></algorithm></cstdio>…

普通に平均最大化をする。小数の闇を見た。 #include <cstdio> #include <algorithm> #include <functional> #include <iostream> #include <math.h> using namespace std; int n,k,d[1002][2]; double t[1002]; bool ch(double x){ for(int i = 0;i < n;i++){ t[i] = 100.00 * d[i][0] - x * d[i][1]; } sort(</math.h></iostream></functional></algorithm></cstdio>…

もう解きたくない・ 黒歴史ソース #include <cstdio> #include <algorithm> using namespace std; const int INF = 1000000002; int n,k,d[100003]; bool ch( long long int x){ long long int u = 0; for(int i = 0;i < n;i++){ if(d[i] > x){ u += (d[i] - x + k -2)/(k-1); }</algorithm></cstdio>…

二分探索で最小値を求める。 #include <cstdio> using namespace std; const int INF = 100002; int n,m,d[1000002]; bool ch(int x){ int u = 1; int sum = 0; for(int i = 0;i < n;i++){ if(d[i] > x)return false; if(d[i] + sum > x){ u++; sum = d[i]; }else{ s</cstdio>…

顕著な二分探索。説明不要な気がする。 #include <cstdio> #include <algorithm> using namespace std; const int INF = 1000000001; int l,n,m,d[50001]={0}; bool ch(int x){ int u = 0; int pre = 0; for(int i = 1;i <= n+1;i++){ if(d[pre] + x > d[i]){ u++; }else{ pre =</algorithm></cstdio>…

蟻本にある。 二分探索使わなくても解けるのだろうか。 #include <cstdio> #include <algorithm> using namespace std; const int INF = 1000000001; int n,c,p[100001]; bool ch(int x){ int nau = 0,sum = 1,pre = p[nau]; while(nau < n && sum < c){ if(pre + x <= p[nau]){</algorithm></cstdio>…

解法：最長増加部分列(LIS)蟻ゲーです。 #include <cstdio> #include <algorithm> const int INF = 100000000; using namespace std; int main(){ int n; scanf("%d",&n); while(n--){ int p; int d[40003]={0}; int dp[40003] = {0}; scanf("%d",&p); for(int i = 0;i < p;i++)</algorithm></cstdio>…

なんとか通りました。つかれた。問題文はこちら世界スパッゲッティソース大会で決勝にいけそうなソースです。joi本選の練習も兼ねて、mapとかvectorとかqueueとかpairとかいろんなの使ってみました。 なのでとても複雑になってしまった。。。実行時間もそこ…

問題文はこちら。 瞬殺問題。 二分探索地味に初めてでした。 一発ACはたのしい。 #include <cstdio> #include <algorithm> #include <vector> using namespace std; int main(){ while(1){ long int d = 0; long int n = 0; int m = 0; long int ans = 0; vector<long> dat; vector<long>::iterator </long></long></vector></algorithm></cstdio>…