P1281 书的复制

​​传送门​​

思路：

对每个人抄书的页数进行二分，最后因为是尽量让前面的人少抄写，所以应该从后往前遍历。

#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
#define ll long long
int a[1010];
int ans[1010];

int m, k;
bool check(int x)
{
  int cnt = 0, sum = 0;
  for (int i = 1; i <= m; i++)
  {
    if (sum + a[i] > x)
    {
      sum = 0;
      cnt++;
    }
    sum += a[i];
  }
  return cnt >= k;
}
int main()
{
  int l = 0, r = 0;
  cin >> m >> k;
  for (int i = 1; i <= m; i++)
  {
    cin >> a[i];
    r += a[i];
  }
  while (l < r)
  {
    int mid = l + r >> 1;
    if (check(mid))
    {
      l = mid + 1;
    }
    else
    {
      r = mid ;
    }
  }
  int sum = 0;
  int cnt = 0;
  for (int i = m; i >= 1; i--)
  {
    if(sum + a[i] > l)
    {
      ans[cnt++] = i+1;
      sum = 0;
    }
    if(sum == 0)
    {
      ans[cnt++] = i;
    }
    sum += a[i];
    if(i == 1)
    {
      ans[cnt++] = i;
    }
  }
  for(int i = cnt-1; i >= 1; i-=2)
  {
    printf("%d %d\n",ans[i],ans[i-1]);
  }
}