T1
还算是一道简单题,通过二分可以轻松求解。(但是我因为没有判断左端点挂了 \(10pts\) ,不然我就是本场比赛的 \(rk1\) 了)
虽然题解上说单调性是错误的,但是而二分能过,那就二分水过去吧。
int n,k;
int a[2050];
bool vis[2050];
inline int work(int x){
memset(vis,0,sizeof vis);
int ans=0;
up(i,1,n){
int res=x,flg=0;
up(j,1,n){
if(vis[j])continue;
if(res>=a[j]){
res-=a[j];
vis[j]=1;
flg=1;
}
if(res==0)break;
}
if(flg)ans++;
}
return ans;
}
inline bool cmp(int x,int y){
return x>y;
}
signed main(){
n=read();k=read();
int maxl=0;
up(i,1,n){
a[i]=read();
maxl=max(maxl,a[i]);
}
sort(a+1,a+1+n,cmp);
int l=maxl,r=1e7,ans;
while(l<=r){
int mid=(l+r)>>1;
if(work(mid)<=k){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
cout<<ans;
return 0;
}
T2
完成成就:考场干黑(?或许)。
做题的时候还觉得没什么,考完后看一下题解,发现我怎么这么 nb,竟然搞出这道题。
这还是一道博弈论(最近怎么这么多博弈论)。
看着似乎很不好搞的样子,