牛客小白月赛26 A 牛牛爱学习

Description

疫情期间，牛牛宅在家里无事可做，于是就在网上买了n本书，每本书都有一个知识值为ai。每读一本书，牛牛的知识力就会上升ai点。当然了，因为牛牛的精力也是有限的，如果同一天连续读k本书，获得的知识力只能增加ai-k+1点。比如第一天看了知识值为5的书，那么牛牛会获得5点知识力，如果这一天在继续看另一本知识值为5的书，只能获得4点知识力，如果看了前面两本书后在继续看一本知识值为2的书，就只能获得0点知识力。牛牛想知道如果他要获得m点知识力，最少需要看几天。

注意：看书不需要按顺序，一本书只能看一次，书可以不看完，只要看就会增加知识力，当书增加的知识力为负时候可以选择不看，可以认为看完一本书是一瞬间的事情，看完后书就会消失。

Solution

Codeforces Round #540 (Div. 3) 原题
二分思路并不难想，考虑对贡献值从大到小排序
每次选取最大贡献的书，然后check的时候每走完x天，维护一个tot
简单的讲，就是第一轮先把每一天都用贡献最大的填上，然后第二轮填的时候每一本书的贡献就都要减1，这样不断填充就行了。

Code

#include<bits/stdc++.h>
typedef long long ll;
const int N = 1e6 + 5;
const int mod = 1e4 + 7;
using namespace std;
ll a[N], c[N];
int n, m;
bool check(int x) {
  ll res = 0, tot = 0, now = 0;
  for(int i = 1; i <= n; i++) {
    now++; res += max(0LL, a[i] - tot);
    if(now == x) {
      tot++, now = 0;
    }
  }
  return res >= m;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> a[i];
  sort(a + 1, a + 1 + n, greater<int>());
  int left = 1, right = 1e9;
  int ans = -1;
  while(left <= right) {
    int mid = left + right >> 1;
    if(check(mid)) {
      right = mid - 1;
      ans = mid;
    } else {
      left = mid + 1;
    }
  }
  cout << ans << "\n";
  return 0;
}