AtCoder Grand Contest 011 AB欲張り、二分

6909 ワード
欲が深い 二分
A - Airport Bus
時間制限:2 sec/Memory制限:256 MB
配点:300点
問題文
高桥机场每天飞机到达了N人的乘客.第i号乘客到达时刻Ti.
到达高桥机场的乘客全员乘坐巴士移动到市内.哪个巴士都可以乘坐C人,可以乘坐C人以下的乘客.飞机的乘客可以乘坐比飞机的到达时刻更早出发的巴士.另外,飞行机到达时间K的时间过后也没有乘坐巴士的话,我生气了.因此,第i号的乘客,不能乘坐在Ti以上Ti+K以下的巴士.
从这个条件来看,如果马上决定巴士的出发时刻的话,请需求必要的巴士数量的最小值.但是,巴士的出发时刻不一定是整数的必要,同一时间出发的巴士不多.
制約
2≤N≤100000
1≤C≤109
1≤K≤109
1≤Ti≤109
C,K,Tiは整数にゅうりょく
入力由以下形式提供标准入力.
N C K
T1
T2
:
TN

力を出す
把必要的巴士数的最小值出力啊.
入力例1
Copy 
5 3 5
1
2
3
6
12

出力例1
Copy 
3

例如,时间4.5,6,12让巴士出发,如下乘客乘坐巴士就好了.
出发时间4.5的巴士,乘坐到达时间2,3的乘客.出发时刻6的巴士,乘坐到达时刻1,6的乘客.出发时刻12的巴士,乘坐到达时刻12的乘客.入力例2
Copy 
6 3 3
7
6
2
8
10
6

出力例2
Copy 
3

标题:大勢の乗客が空港までシャトルバスで市街地に戻り、乗客一人一人が到着する時間はtiで、シャトルバスは最大c人を収容し、一人の乗客がk時間以上待つと彼は怒り、すべての乗客が怒らないようにする最低シャトルバス数を求めた.
むやみに書く
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1e5+10;
int n,c,k;
long long t[maxn];
int findpos(int left,long long x){
    int right = n;
    while (right-left>1) {
        int middle = (left+right)/2;
        if(t[middle]>=x){
            right = middle;
        }else{
            left = middle;
        }
    }
    int pos = left;
    if(t[right]<=x){
        pos = right;
    }
    return pos;
}
bool vis[maxn];
int main(){
    int i,j;
    scanf("%d%d%d",&n,&c,&k);
    for(i=1;i<=n;i++){
        scanf("%lld",t+i);
    }
    sort(t+1, t+1+n);
    memset(vis, true, sizeof(vis));
    int p = 1;
    int kpos;
    long long res = 0;
    int last = -1;
    while(vis[n]){
        kpos = findpos(p, t[p]+k);
        int another = (kpos-p+1)%c;
        res += (kpos-p+1)/c;
        for(i=p;i<=kpos-another;i++){
            vis[i] = false;
        }
        p = kpos - another+1;
        if(p == last){
            res++;
            for(i=p;i<=kpos;i++){
                vis[i] =false;
            }
            p = kpos + 1;
            continue;
        }
        last = p;
    }
    printf("%lld
",res);
    return 0;
}

B - Colorful Creatures
時間制限:2 sec/Memory制限:256 MB
配点:400点
問題文
ぬけ君发现了N匹的变化活动物.各自的活动物中定了颜色和大小,第i的活动物的颜色是i,大小是Ai.
どの生き物でも、大きさが自分の2倍以下のような他の生き物を吸い取ることができます.大きさA、色Bの生き物が大きさC、色Dの生き物を吸い取ると(C≦2)×A),合体成为大度A+C,颜色B的生存物.在这里,根据2匹的生存物的大小,哪个都可以吸收其他人.
如果你观察这个生存物们的话,重复合体,最终成为一只.此时,作为剩下的生存物的颜色考虑到的东西有什么类型.
制約
2≤N≤100000
1≤Ai≤109
Ai是整数にゅうりょく
入力由以下形式提供标准入力.
N
A1 A2 … AN

力を出す
这个生物们重复合体,最终成为1匹的时候,作为剩下的生物的颜色来考虑到的是什么东西的呐?
入力例1
Copy 
3
3 1 4

出力例1
Copy 
2

最后剩下的生物的颜色是颜色1,3.例如,颜色3的生物吸收颜色2的生物,接下来颜色1的生物和颜色3的生物合体,只剩下颜色1的生物.
入力例2
Copy 
5
1 1 1 1 1

出力例2
Copy 
5

也有很多同样的大小的生物.
入力例3
Copy 
6
40 1 30 2 7 20

出力例3
Copy 
4

タイトル:
高橋(南)君は、n個目とi番目の生物の色がiである奇妙な生物を発見した.この生物には、aの体重の2倍がbの体重より大きいと、aはbを吸収し、体重がa+bで、色が元のaの色の生物になるという融合法則がある
今ではいつもこのn人の生物を吸収して最后に1匹になって、最后にそれがどれだけ异なる色を植えることができるかを闻きます
問題を読み間違えて長い間詰まっていた...
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1e5+10;
int n;
long long save[maxn];
long long eat[maxn];
bool check(int pos){
    int i,j;
    long long now = save[pos];
    for(i=1;i<=n;i++){
        if(i==pos){
            continue;
        }
        if(save[i]<=now*2){
            now += save[i];
        }
        if(now*2>=save[n]){
            return true;
        }
        if(save[i]>now*2){
            return false;
        }
    }
    return true;
}
int main(){
    scanf("%d",&n);
    int i,j;
    eat[0] = 0;
    for(i=1;i<=n;i++){
        scanf("%lld",&save[i]);
        eat[i] = eat[i-1]+save[i];
    }
    sort(save+1, save+1+n);
    int left = 1,right = n;
    while(right-left>1){
        int middle = (left+right)/2;
        if(check(middle)){
            right = middle;
        }else{
            left = middle;
        }
    }
    int res = right;
    if(check(left)){
        res = left;
    }
    cout<
Linuxのインストールとアンインストール
forサイクル中のbreakとcontinue