Codeforce Round #515 div3 Boxes Packing_maksim has n objects and m boxes, each box has siz

Codeforce Round #515 div3 Boxes Packing

题目:
Maksim has n objects and m boxes, each box has size exactly k. Objects are numbered from 1 to nn in order from left to right, the size of the i-th object is ai.Maksim wants to pack his objects into the boxes and he will pack objects by the following algorithm: he takes one of the empty boxes he has, goes from left to right through the objects, and if the i-th object fits in the current box (the remaining size of the box is greater than or equal to ai), he puts it in the box, and the remaining size of the box decreases by ai. Otherwise he takes the new empty box and continues the process above. If he has no empty boxes and there is at least one object not in some box then Maksim cannot pack the chosen set of objects.Maksim wants to know the maximum number of objects he can pack by the algorithm above. To reach this target, he will throw out the leftmost object from the set until the remaining set of objects can be packed in boxes he has. Your task is to say the maximum number of objects Maksim can pack in boxes he has.Each time when Maksim tries to pack the objects into the boxes, he will make empty all the boxes he has before do it (and the relative order of the remaining set of objects will not change).

Input
The first line of the input contains three integers nn, mm, kk (1≤n,m≤2⋅10^5,1≤n,m≤2⋅ 10^5, 1≤k≤10^9,1≤k≤10 ^9) — the number of objects, the number of boxes and the size of each box.The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤k,1≤ai≤k), where aiai is the size of the ii-th object.

题目大意是给出一组物品各有大小，然后给出m个容器容量为k，从左往右装看是否能装完,如果装不完就丢弃第一件物品，从第二件物品开始重新装看是否能装完。问最大能装几件物品。

分析一下，这是在问从第几件物品开始装可以装完，装的物品数量其实就是终点减去起点.可以写一个判断函数，给定起点判断从该起点能否装完,接下来常规思路就是从第一件物品开始遍历，直到找到第一个能装完的起点，然后终点减去起点就是答案了。似乎这样做也不会超时，这题也可以用二分做 下面贴出代码(不会搞缩进):

#include<iostream>
using namespace std;
#define MAX 200010
#include<algorithm>
#include<string.h>
int boxs[MAX];
int obj[MAX];
int n,m,k;
int f(int mid)
{
 int k=1;
 for(int i=mid;i<=n;i++)
 {
  if(boxs[k]<obj[i])
   k++;
  if(k>m)
   return 0;
  boxs[k]-=obj[i];
 }
 return 1;
}
int main()
{
 scanf("%d%d%d",&n,&m,&k);
 fill(boxs,boxs+m+2,k);
 for(int i=1;i<=n;i++)
  scanf("%d",&obj[i]);
 int L=1,R=n;
 while(L!=R)
 {
  fill(boxs,boxs+m+2,k);
  int mid=(L+R)>>1;
  if(f(mid))
   R=mid;
  else
   L=mid+1;
 }
 printf("%d\n",n-L+1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38