|
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
39
40
41
42
43
44
45
46
47 |
BillboardTime Limit: 20000/8000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 8663 Accepted Submission(s): 3862Problem DescriptionAt the entrance to the university, there is a huge rectangular billboard of size h*w (h is its height and w is its width). The board is the place where all possible announcements are posted: nearest programming competitions, changes in the dining room menu, and other important information.On September 1, the billboard was empty. One by one, the announcements started being put on the billboard.Each announcement is a stripe of paper of unit height. More specifically, the i-th announcement is a rectangle of size 1 * wi.When someone puts
a new
announcement on the billboard, she would always choose the topmost possible position for
the announcement. Among all possible topmost positions she would always choose the leftmost one.If there is no valid location for
a new
announcement, it is not put on the billboard (that‘s why some programming contests have no participants from this
university).Given the sizes of the billboard and the announcements, your task is to find the numbers of rows in which the announcements are placed. InputThere are multiple cases (no more than 40 cases).The first line of the input file contains three integer numbers, h, w, and n (1 <= h,w <= 10^9; 1 <= n <= 200,000) - the dimensions of the billboard and the number of announcements.Each of the next n lines contains an integer number wi (1 <= wi <= 10^9) - the width of i-th announcement. OutputFor each announcement (in the order they are given in the input file) output one number - the number of the row in which this
announcement is placed. Rows are numbered from 1 to h, starting with the top row. If an announcement can‘t be put on the billboard, output "-1"
for this announcement. Sample Input3 5 524333 Sample Output1213-1 |
为什么c++和c语言的运行速度差距这么大啊，c++超时，c只要2000ms。
#define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #define MAX 605000 #define Lc(e) (e<<1) #define Rc(e) ((e<<1)+1) #define Half(e) (e>>1) using namespace std; struct STREE{ int m, lc, rc; }; STREE stree[MAX]; int n, h, w; int row[MAX];//行号 //void Init(){ // memset(row, -1, sizeof(row)); //} void BuildTree(int i, int l, int r){ stree[i].m = w;//最大为广告栏的宽度 stree[i].lc = l; stree[i].rc = r; if (l == r)return; BuildTree(Lc(i), l, Half(l + r)); BuildTree(Rc(i), Half(l + r)+1, r); } int Insert(int i, int x){ //相当于修改叶节点的最大值 if (stree[i].m < x)return -1;//总区间内都小于x，没有空给你贴广告了^o^ if (stree[i].lc == stree[i].rc){ stree[i].m -= x; return stree[i].lc; } int res = -1;//不在这设一个res作为返回值，程序就不能运行到max那一步，唉，没道理啊，有返回值得更新都得这样么 if (stree[Lc(i)].m >= x){ res = Insert(Lc(i), x); } else{ res = Insert(Rc(i), x); } if (stree[Lc(i)].m > stree[Rc(i)].m)stree[i].m = stree[Lc(i)].m; else stree[i].m = stree[Rc(i)].m; //stree[i].m = max(stree[i * 2].m, stree[i * 2 + 1].m); return res; } int main() { int t; while (scanf("%d %d %d", &h, &w, &n) != -1){ //Init(); BuildTree(1, 1, min(h, n));//在这里设个比较是因为如果h小于n的时候，你建的叶节点就会有多余。。。不信你试试 for (int i = 0; i < n; i++){ scanf("%d", &t); row[i] = Insert(1, t); //cout << row[i] << endl; } for (int i = 0; i < n; i++)printf("%d\n", row[i]); } return 0; }
原文：http://www.cnblogs.com/littlehoom/p/3575582.html