2019/3/16バイトジャンプ筆記試験問題
n人がプログラミング試合に参加し、試合が終わった後、誰もが点数を取った.今、すべての人が1周目(1番目とn番目に隣接)に並んで賞品を受け取り、要求しています.1:ある人の点数が左右の人より高いと、賞品の数も左右の人より多い.2:一人一人が少なくとも賞品をもらう.少なくとも賞品はいくら用意すべきかを聞く.
説明を入力:
第1行は整数nであり、試験サンプルの個数を表す各試験サンプルの第1行は正の整数nであり、試合に参加する人数を表す.(0 2行目はn個の正の整数a[i](0 出力説明:各テストサンプルに対して、準備すべき最低限の賞品を出力します。サンプル:2 2 1 2 4 1 2 3出力3 8考え方:実は左から右へ1回遍歴して、1つのシーケンスを得て、それから右から左へ遍歴して、2番目のシーケンスを得て、それから最後に大きい値を取って、最後に累積すればいいです。コード: カバー力: #include #include #include using namespace std; const int MAX = 100000+10; int a[MAX]; int ans1[MAX]; int ans2[MAX]; int main() { int n,t; scanf("%d",&t); while(t--) { scanf("%d",&n); int min_index = 0; for(int i=0;ia[cur]) ans1[next] = ans1[cur] +1 ; else ans1[next] = 1; cur = (cur+1)%n; next = (cur+1)%n; } cur = min_index; next = (cur-1+n)%n; ans2[min_index] = 1; flag = false; while(cur!= min_index || !flag) { flag = true; if(a[next]>a[cur]) ans2[next] = ans2[cur] +1 ; else ans2[next] = 1; cur = (cur-1 +n)%n; next = (cur-1+n)%n; } int ans = 0; for(int i = 0 ;i < n ;i++) ans += max(ans1[i],ans2[i]); printf("%d",ans); } return 0; } 2番目の問題: Nとロープがあって、i本目のロープの長さはLiで、今M本などの長いロープが必要で、あなたはn本のロープに対して任意に裁断することができて(つなぎ合わせることができません)、あなたはこのm本のロープの最も長い長さがどれだけあるかを計算してください。 入力説明：最初の行は2つの正の整数N，Mを含んで、N本の原始の縄を表して、そして最終的にMと縄の第2の行はN個の整数を含んで、第iの整数Liは第i本の縄の長さを表します そのうち1<=N、M<=1000000<Li<10000000000 入力3 4 3 5 4 出力2.5 解析:2分、ロープの長さを2分して、M個以上の等長条件を満たすかどうかを見ます。 コード: カバー力: #include #include #include using namespace std; #define eps 1e-6 const int maxn = 100000+10; double a[maxn]; bool Judge(double mid, int n, int m) { int cnt = 0; for(int i = 0 ;i=m) return true; return false; } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { double l,r,mid; r = -1; for(int i=0;ieps) { mid = (l+r)/2; if(Judge(mid,n,m)) l = mid; else r = mid; } printf("%.2f",l); } return 0; }
説明を入力:
第1行は整数nであり、試験サンプルの個数を表す各試験サンプルの第1行は正の整数nであり、試合に参加する人数を表す.(0 2行目はn個の正の整数a[i](0 出力説明:各テストサンプルに対して、準備すべき最低限の賞品を出力します。サンプル:2 2 1 2 4 1 2 3出力3 8考え方:実は左から右へ1回遍歴して、1つのシーケンスを得て、それから右から左へ遍歴して、2番目のシーケンスを得て、それから最後に大きい値を取って、最後に累積すればいいです。コード: カバー力: #include #include #include using namespace std; const int MAX = 100000+10; int a[MAX]; int ans1[MAX]; int ans2[MAX]; int main() { int n,t; scanf("%d",&t); while(t--) { scanf("%d",&n); int min_index = 0; for(int i=0;ia[cur]) ans1[next] = ans1[cur] +1 ; else ans1[next] = 1; cur = (cur+1)%n; next = (cur+1)%n; } cur = min_index; next = (cur-1+n)%n; ans2[min_index] = 1; flag = false; while(cur!= min_index || !flag) { flag = true; if(a[next]>a[cur]) ans2[next] = ans2[cur] +1 ; else ans2[next] = 1; cur = (cur-1 +n)%n; next = (cur-1+n)%n; } int ans = 0; for(int i = 0 ;i < n ;i++) ans += max(ans1[i],ans2[i]); printf("%d",ans); } return 0; } 2番目の問題: Nとロープがあって、i本目のロープの長さはLiで、今M本などの長いロープが必要で、あなたはn本のロープに対して任意に裁断することができて(つなぎ合わせることができません)、あなたはこのm本のロープの最も長い長さがどれだけあるかを計算してください。 入力説明：最初の行は2つの正の整数N，Mを含んで、N本の原始の縄を表して、そして最終的にMと縄の第2の行はN個の整数を含んで、第iの整数Liは第i本の縄の長さを表します そのうち1<=N、M<=1000000<Li<10000000000 入力3 4 3 5 4 出力2.5 解析:2分、ロープの長さを2分して、M個以上の等長条件を満たすかどうかを見ます。 コード: カバー力: #include #include #include using namespace std; #define eps 1e-6 const int maxn = 100000+10; double a[maxn]; bool Judge(double mid, int n, int m) { int cnt = 0; for(int i = 0 ;i=m) return true; return false; } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { double l,r,mid; r = -1; for(int i=0;ieps) { mid = (l+r)/2; if(Judge(mid,n,m)) l = mid; else r = mid; } printf("%.2f",l); } return 0; }