题目链接:2017 ACM-ICPC 筑波区域赛 C:Medical Checkup
Description
有n个人依次进行检查,第i个人进行每项检查所需的时间都是h[i]。
问在t时刻每个人正在进行或等待第几项检查,每个项目只能做一个人。
Sample Input
3 20
5
7
3
Sample Output
5 3 2
Solution
每个人实际上消耗的时间关键是ta前面最慢的那个人。
在进行第一项检查前,需要等待前面的所有人检查完毕。
而进行后面的项目时只需等待前面一个人检查完即可。
因此第一次检查的实际用时就是的前缀和
而后面各项检查的实际用时,
即如果前面一个人比后面的慢,就可以将这二者合并,
此时后面人的等待时间必然是。
最后的结果是。
Code
#include<map> #include<set> #include<list> #include<queue> #include<vector> #include<string> #include<time.h> #include<math.h> #include<stdio.h> #include<stdlib.h> #include<string.h> #include<iostream> #include<algorithm> //#define Judge //#define Online #define maxn 200100 #define reg register #define ll long long #define mod 1000000007 #define inf 2147483647 #define lowbit(x) ((x)&-(x)) #define abs(x) ((x)<0?-(x):(x)) #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define isd(c) ('0'<=(c)&&(c)<='9') #define isa(c) ('a'<=(c)&&(c)<='z') #define isA(c) ('A'<=(c)&&(c)<='Z') #define ckmax(a,b) ((a)=max((a),(b))) #define ckmin(a,b) ((a)=min((a),(b))) using namespace std; #ifdef Judge #define puts io.put #define getchar io.gc #define putchar io.wchar #ifdef Online FILE*in=stdin; FILE*out=stdout; #else FILE*in=fopen(".in","r+"); FILE*out=fopen(".out","w+"); #endif struct FastIO{ #define S 1000000 int wpos,len,pos;char wbuf[S],buf[S]; FastIO(){wpos=0,len=0,pos=0;} inline char gc(){ if (pos==len) pos=0,len=fread(buf,1,S,in); if (pos==len) return 0; return buf[pos++]; } inline void wchar(int x) { if (wpos==S) fwrite(wbuf,1,S,out),wpos=0; wbuf[wpos++]=x; } inline void put(const char*s) {for(; *s; ) wchar(*s++);} ~FastIO() { if (wpos) fwrite(wbuf,1,wpos,out),wpos=0; } }io; #endif template<typename T> inline void read(T&x){T f=1;x=0;char c; for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f; for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f; } template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-'); int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c); } ll n,t,cnt,m,q; int main(int argv,char*argc[]){ read(n),read(t),cnt=0,m=-inf; for (int i=1; i<=n; i++) read(q),ckmax(m,q),cnt+=q, wt((t>=cnt)?(t-cnt)/m+2:1,'\n'); return 0; }