A:月度开销
描述
农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。
约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案,他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天,每天被恰好包含在一个fajo月里。
约翰的目标是合理安排每个fajo月包含的天数,使得开销最多的fajo月的开销尽可能少。
输入
第一行包含两个整数N,M,用单个空格隔开。
接下来N行,每行包含一个1到10000之间的整数,按顺序给出接下来N天里每天的开销。
输出
一个整数,即最大月度开销的最小值。
样例输入
7 5 100 400 300 100 500 101 400
样例输出
500
提示
若约翰将前两天作为一个月,第三、四两天作为一个月,最后三天每天作为一个月,则最大月度开销为500。其他任何分配方案都会比这个值更大。
1 #include<iostream> 2 using namespace std; 3 int a[100005]; 4 int n, m; 5 bool check(int mid){ 6 int cursum = 0; 7 int temp = 1; //注意是1 8 for(int i = 0; i < n; i++){ 9 if(cursum+a[i]>mid){ //超了 10 temp++; //fajo月 11 cursum = a[i]; 12 } 13 else cursum += a[i]; 14 } 15 if(temp > m) return false; 16 return true; 17 } 18 int main(){ 19 cin>>n>>m; 20 int l = 0, r = 0; 21 for(int i = 0; i < n; i++){ 22 cin>>a[i]; 23 l = max(l, a[i]); 24 r += a[i]; 25 } 26 int mid; 27 while(l <= r){ 28 mid = l + (r-l)/2; 29 bool flag = check(mid); 30 if(flag) r = mid-1; 31 else l = mid+1; 32 } 33 cout<<mid<<endl; 34 return 0; 35 }
备注:二分的题都很套路。首先是卡范围,最小的可能值显然就是最多的一天,最大的可能值是所有天之和。然后就是check函数,怎么验证一个解对不对,一般就用到贪心。注意括号里是l<=r,否则假如答案是50,l是50,r是52,mid是51,check过了之后r变为50,不满足l<r直接退出了,那么答案就不是最小的。这道题就是尽可能把更多的天塞进一个fajo。因为一个月如果本可以塞前一个fajo里却没塞,相当于一种浪费,因为它就要占据后面的空间。这样塞完之后得到的fajo月如果小于等于我们正在尝试的mid就是一个可行的解。
B:派
描述
我的生日要到了!根据习俗,我需要将一些派分给大家。我有N个不同口味、不同大小的派。有F个朋友会来参加我的派对,每个人会拿到一块派(必须一个派的一块,不能由几个派的小块拼成;可以是一整个派)。
我的朋友们都特别小气,如果有人拿到更大的一块,就会开始抱怨。因此所有人拿到的派是同样大小的(但不需要是同样形状的),虽然这样有些派会被浪费,但总比搞砸整个派对好。当然,我也要给自己留一块,而这一块也要和其他人的同样大小。
请问我们每个人拿到的派最大是多少?每个派都是一个高为1,半径不等的圆柱体。
输入
第一行包含两个正整数N和F,1 ≤ N, F ≤ 10 000,表示派的数量和朋友的数量。
第二行包含N个1到10000之间的整数,表示每个派的半径。
输出
输出每个人能得到的最大的派的体积,精确到小数点后三位。
样例输入
3 3 4 3 3
样例输出
25.133
1 #include<iostream> 2 #include<cmath> 3 using namespace std; 4 double a[10005]; 5 int n, f; 6 //注意数据类型是double 7 const double pi = acos(-1); //求派的巧妙方法 8 bool check(double mid){ 9 int temp = 0; 10 for(int i = 0; i < n; i++) 11 temp += a[i]/mid; 12 return temp >= f+1; //别忘了加上自己 13 } 14 int main(){ 15 cin>>n>>f; 16 double l = 0, r = 0; 17 int semi; 18 for(int i = 0; i < n; i++){ 19 cin>>semi; 20 a[i] = pi * semi * semi; //存体积 21 r = max(r, a[i]); 22 } 23 double mid; 24 while(r-l > 1e-5){ 25 mid = l + (r-l)/2; 26 bool flag = check(mid); 27 if(flag) l = mid; 28 else r = mid; 29 } 30 printf("%.3lf", mid); 31 return 0; 32 }
备注:这道题要注意的就是输入数据是半径,但问的是体积(高是1,所以相当于面积),所以数组里要存的也是面积。还有一点就是所有的数据类型都要是double!最开始我就是忽略了形参mid也应该是double所以得不出正确答案。既然是double,就不能用简单的=或者<>,而要用ε,这里取的是1e-5。
C:河中跳房子
描述
每年奶牛们都要举办各种特殊版本的跳房子比赛,包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行,在起点和离起点L远 (1 ≤ L≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间,有N (0 ≤ N ≤ 50,000) 个岩石,每个岩石与起点的距离分别为Di (0 < Di < L)。
在比赛过程中,奶牛轮流从起点出发,尝试到达终点,每一步只能从一个岩石跳到另一个岩石。当然,实力不济的奶牛是没有办法完成目标的。
农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移,看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行,他感到非常厌烦。他计划移走一些岩石,使得从起点到终点的过程中,最短的跳跃距离最长。他可以移走除起点和终点外的至多M (0 ≤ M ≤ N) 个岩石。
请帮助约翰确定移走这些岩石后,最长可能的最短跳跃距离是多少?
输入
第一行包含三个整数L, N, M,相邻两个整数之间用单个空格隔开。
接下来N行,每行一个整数,表示每个岩石与起点的距离。岩石按与起点距离从近到远给出,且不会有两个岩石出现在同一个位置。
输出
一个整数,最长可能的最短跳跃距离。
样例输入
25 5 2 2 11 14 17 21
样例输出
4
提示在移除位于2和14的两个岩石之后,最短跳跃距离为4(从17到21或从21到25)。
1 #include<iostream> 2 using namespace std; 3 int a[50005]; 4 int L, n, m; 5 6 bool check(int mid){ 7 int last = 0; 8 int temp = 0; 9 for(int i = 0; i <= n; i++){ 10 if(a[i]-last<mid){ 11 temp++; //移走 12 continue; 13 } 14 last = a[i]; 15 } 16 17 if(temp > m) return false; 18 return true; 19 } 20 int main(){ 21 cin>>L>>n>>m; 22 int r = L, l = 0; 23 for(int i = 0; i < n; i++){ 24 cin>>a[i]; 25 } 26 a[n] = L; 27 int mid, ans; 28 while(l <= r){ 29 mid = l + (r-l)/2; 30 bool flag = check(mid); 31 if(flag){ 32 l = mid+1; 33 ans = mid; 34 } 35 else r = mid-1; 36 } 37 cout<<ans<<endl; 38 return 0; 39 }
备注:这道题和我多年前写过的跳石头是一样的,好像是noip真题。但是首先是我又不会了,其次是我发现当时写的有一点小错(没考虑最后一块砖),过了是因为数据水……要注意的第一点是要把a[n] = L也就是最后一块石头补上。(最后一块石头是移不了的,但这不影响结果,因为在check的时候,如果发现a[n]-last不合要求,移走的其实是last那块石头。因为last距离倒数第三块石头一定是满足要求的,移走它,倒数第三块石头离最后一块石头肯定也是足够的)。
还有一点是上次也强调过的。这道题的答案写mid就不行,举个例子,如果答案是51,l是50,r是52,那么mid是51,然后check过了,l变成52,l依然<=r,这个时候依然进入循环,mid是52,但mid可能没通过check,这个时候r变成51,跳出了循环,但这个时候mid就不是正确答案。解决办法就是设置一个ans,保证是check过的。