[Luogu 2816]宋荣子搭积木

Description

saruka非常喜欢搭积木，他一共有n块积木。而且saruka的积木很特殊，只能一块块的竖着摞，可以摞很多列。说过saruka的是特殊的积木了，这些积木都非常智能，第i块积木有一个情绪值xi，当摞在这块积木上的积木总数超过xi时，这块积木就会很不高兴，发誓以后不会再和saruka一起玩耍了。saruka这么爱玩积木，肯定不会让积木不高兴的，但是saruka又希望每块积木都被用上，并且摞的积木列数最少。你能来帮帮saruka嘛？

Input

第一行一个整数n，含义如题目描述所示

第二行有n个数xi，含义如题目描述所示

Output

输出一个数字，代表最小的积木列数

Sample Input

3

0 0 10

Sample Output

HINT

1 <= n <= 5000

xi <= n

题解

题解都是从小到大排序...然后一个一个丢进去....

但是考场上想到的是二分...也过了...

我们将$x$排序从大到小，二分答案，将这$n$个数：第$i$个数放在$i$ $mod$ $mid$的堆上。边遍历边判断是否可行。

感觉应该也没问题...也不会证（大概就是尽可能地利用了$x$吧...）

 //It is made by Awson on 2017.10.5

 #include <map>

 #include <set>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <vector>

 #include <cstdio>

 #include <string>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define sqr(x) ((x)*(x))

 using namespace std;

 const int N = ;

 void read(int &x) {

   char ch; bool flag = ;

   for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());

   for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());

   x *= -*flag;

 }

 int n, a[N+];

 bool comp(const int &a, const int &b) {

   return a > b;

 }

 bool judge(int mid) {

   int rest[N+];

   for (int i = ; i <= mid; i++)

     rest[i] = a[i];

   for (int i = mid+; i <= n; i++) {

     int t = i%mid;

     if (!t) t = mid;

     rest[t] = Min(rest[t]-, a[i]);

     if (rest[t] < ) return false;

   }

   return true;

 }

 void work() {

   read(n);

   for (int i = ; i <= n; i++) read(a[i]);

   sort(a+, a+n+, comp);

   int l = , r = n, ans = n;

   while (l <= r) {

     int mid = (l+r)>>;

     if (judge(mid)) ans = mid, r = mid-;

     else l = mid+;

   }

   printf("%d\n", ans);

 }

 int main() {

   work();

   return ;

 }

秒客网