時間制限 : 2sec / メモリ制限 : 256MB
配点 : 300 点
高橋空港には，毎日飛行機で N 人の乗客が到着します． i 番目の乗客は時刻 Ti に到着します．
高橋空港に到着する乗客は全員バスで市内へ移動します．どのバスも定員は C 人であり，C 人以下の乗客を乗せることができます． 飛行機の乗客は，飛行機の到着時刻よりも早く出発するバスには乗ることができません． また，飛行機の到着時刻から K の時間が経過した後にもバスに乗れていないと，怒り出してしまいます． そのため，i 番目の乗客は，出発時刻が Ti 以上 Ti+K 以下であるようなバスに乗れるようにしないといけません．
この条件のもとで，うまくバスの出発時刻を定めるとき，必要なバスの数の最小値を求めてください． ただし，バスの出発時刻は必ずしも整数である必要はなく，同じ時刻に出発するバスが複数あってもかまいません．
入力は以下の形式で標準入力から与えられる。
N C K T1 T2 : TN必要なバスの数の最小値を出力せよ．
例えば，時刻 4.5, 6, 12 にバスを出発させ，次のように乗客をバスに乗せるとよいです．
時刻 4.5 に出発するバスには，時刻 2,3 に到着する乗客を乗せる．時刻 6 に出発するバスには，時刻 1,6 に到着する乗客を乗せる．時刻 12 に出発するバスには，時刻 12 に到着する乗客を乗せる．乱写的
#include <iostream> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <algorithm> #include <map> 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\n",res); return 0; }
時間制限 : 2sec / メモリ制限 : 256MB
配点 : 400 点
すぬけ君は，N 匹の変わった生き物を見つけました． それぞれの生き物には色と大きさが定まっており，i 番目の生き物の色は i，大きさは Ai で表されます．
どの生き物も，大きさが自分の 2 倍以下であるような他の生き物を吸収することができます． 大きさ A，色 B の生き物が大きさ C，色 D の生き物を吸収すると (C≤2×A)，合体して大きさ A+C，色 B の生き物になります． ここで，2 匹の生き物の大きさによっては，どちらも他方を吸収することが可能な場合があります．
すぬけ君がこの生き物たちを観察していると，合体を繰り返して，最終的に 1 匹になりました． このとき，残った生き物の色として考えられるものは何種類あるかを求めてください．
入力は以下の形式で標準入力から与えられる。
N A1 A2 … ANこの生き物たちが合体を繰り返して，最終的に 1 匹になったとき，残った生き物の色として考えられるものは何通りあるかを出力せよ．
最終的に残った生き物の色としては色 1, 3 が考えられます． 例えば，色 3 の生き物が色 2 の生き物を吸収し，次に色 1 の生き物が色 3 の生き物と合体すると，色 1 の生き物のみが残ります．
同じ大きさの生き物が複数いる場合もあります．
高桥（南）君发现了一种奇怪的生物，共n个，第i个生物的颜色为i。这种生物存在一种融合规律，即如果a的体重的两倍大于b的体重的话，那么a就能吸收b，并且变成一个体重为a+b，颜色为原本a的颜色的生物
现在总嘟嘟让这n个生物互相吸收最后变成一只，问最后那只将有多少可能种不同颜色
读错题卡了好久。。。
#include <iostream> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <algorithm> #include <map> 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<<n-res+1<<endl; return 0; }
