[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
2
HINT
1 <= n <= 5000
xi <= n
题解
题解都是从小到大排序...然后一个一个丢进去....
但是考场上想到的是二分...也过了...
我们将$x$排序从大到小，二分答案，将这$n$个数：第$i$个数放在$i$ $mod$ $mid$的堆上。边遍历边判断是否可行。
感觉应该也没问题...也不会证（大概就是尽可能地利用了$x$吧...）
1 //It is made by Awson on 2017.10.5 2 #include <map> 3 #include <set> 4 #include <cmath> 5 #include <ctime> 6 #include <queue> 7 #include <stack> 8 #include <vector> 9 #include <cstdio> 10 #include <string> 11 #include <cstdlib> 12 #include <cstring> 13 #include <iostream> 14 #include <algorithm> 15 #define LL long long 16 #define Max(a, b) ((a) > (b) ? (a) : (b)) 17 #define Min(a, b) ((a) < (b) ? (a) : (b)) 18 #define sqr(x) ((x)*(x)) 19 using namespace std; 20 const int N = 5000; 21 void read(int &x) { 22 char ch; bool flag = 0; 23 for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar()); 24 for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar()); 25 x *= 1-2*flag; 26 } 27 28 int n, a[N+5]; 29 bool comp(const int &a, const int &b) { 30 return a > b; 31 } 32 33 bool judge(int mid) { 34 int rest[N+5]; 35 for (int i = 1; i <= mid; i++) 36 rest[i] = a[i]; 37 for (int i = mid+1; i <= n; i++) { 38 int t = i%mid; 39 if (!t) t = mid; 40 rest[t] = Min(rest[t]-1, a[i]); 41 if (rest[t] < 0) return false; 42 } 43 return true; 44 } 45 46 void work() { 47 read(n); 48 for (int i = 1; i <= n; i++) read(a[i]); 49 sort(a+1, a+n+1, comp); 50 int l = 1, r = n, ans = n; 51 while (l <= r) { 52 int mid = (l+r)>>1; 53 if (judge(mid)) ans = mid, r = mid-1; 54 else l = mid+1; 55 } 56 printf("%d\n", ans); 57 } 58 int main() { 59 work(); 60 return 0; 61 }优质内容筛选与推荐>>
1、js 操作 table
2、清除MS sql日志
3、怎样制定公司培训策略
4、codeforce Pashmak and Buses(dfs枚举)
5、uboot SPL