Home > OI > NOIP2010提高组初赛问题求解第三题推广

NOIP2010提高组初赛问题求解第三题推广


我们很自然地想求解下面的问题:

题目:记T为一队列,初始时为空,现有k个总和不超过n的正整数依次入列。如果无论这些数具体为何值,都能找到一种出队的方式,使得存在某个时刻队列T中的数之和恰好为m,那么k的最小值是___________。

显然当m<=0或n<=0或n<m时此题无解,否则:

类似地我们构建下面的图:

0—m—2m—…—m*[n/m]
1—m+1—2m+1—..—m*[n/m]+1
……
n%m—m+n%m—…—n

n%m+1—n%m+1+m—…—n-m+1

m-1—2m-1—…—n-n%m+1
第0行至第n%m行最多总共选([[n/m]/2]+1)(n%m+1)个
第n%m+1行至第m-1行最多总共选[([n/m]+1)/2](m-1-n%m)个
所以总共最多选([[n/m]/2]+1)(n%m+1)+[([n/m]+1)/2](m-1-n%m)个
注意到,我们计算的时候包含了S0,所以k的最小值就是([[n/m]/2]+1)(n%m+1)+[([n/m]+1)/2](m-1-n%m)

以原题n=32, m=9代入,得

k=([32/9]/2+1)*(32%9+1)+[(32/9]+1)/2]*(9-1-32%9)=2*6+2*3=18

Categories: OI Tags: , , , , ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: