九度-1422-Closest Number[数据结构] | Acm之家
1.从左往右遍历，维护一个索引结构的记录数组R[]，和一个索引结构升序栈S[]，依次压入A[i]，同时A[i]左侧的closet number记录R[]为栈顶索引元素，
2.从右往左遍历，可以继续用1中的栈S[]，也可以重新做另一个升序栈SS[]，然后按照1的过程从右往左遍历，比较R[]和S[].
X. Brute Force http://blog.csdn.net/yangnanhai93/article/details/40536263
Read full article from 九度-1422-Closest Number[数据结构] | Acm之家
- There is one Master In ACM_DIY called "白衣少年"(White) whose motto is "I can HOLD ANY FEMALE". Since White is really busy with HOLDING FEMALES, he has no idea of the work that is given by his boss(MALE, of course), so can you help him to solve such a simple and really easy problem:Array A has N positive integers,for each A[i] (0<=i<N, indicating the i-th integer in the array A), it fits in a 32-bit signed integer ),find the closest number less than A[i] (if the distance is the same,we prefer the left one).
If you can solve this problem, White may give you some "tips"(You know better!)
- 输入：
- T cases (1<=T<=5)For each case, the first line give an integer N(1<= N <= 10^6),then the second line has the array with N integers. (All the integers are guaranteed to fit in 32-bit signed integer)
- 输出：
- For each case, print one line with N space-seperated integers, where the i-th integer is the number who is less that A[i] and is closest to i if exists, otherwise it is 0.
- 样例输入：
3 3 2 1 3 3 2 3 1 4 5 7 3 6
- 样例输出：
1 0 1 1 2 0 3 5 0 3给一个数组，对于每个元素a[i]分别找离a[i]最近且小于a[i]的数，如果左右两边距离相同则取左边的数。
1.从左往右遍历，维护一个索引结构的记录数组R[]，和一个索引结构升序栈S[]，依次压入A[i]，同时A[i]左侧的closet number记录R[]为栈顶索引元素，
2.从右往左遍历，可以继续用1中的栈S[]，也可以重新做另一个升序栈SS[]，然后按照1的过程从右往左遍历，比较R[]和S[].
05 | const int NUM=1000001; |
06 | int AA[NUM]={0}; |
07 | struct Rec |
08 | { |
09 | int value; |
10 | int idx; |
11 | }R[NUM],S[NUM]; |
12 | int main() |
13 | { |
14 | int n; |
15 | int num; |
16 | //设置栈0元素。 |
17 | int top=0; |
18 | S[top].value=0; |
19 | S[top].idx =0; |
20 | cin>>n; |
21 | for(int i=0;i<n;i++) |
22 | { |
23 | cin>>num; |
24 | for(int i=1;i<=num;i++) |
25 | { |
26 | cin>>AA[i]; |
27 | R[i].value=0; |
28 | R[i].idx=0; |
29 | } |
30 | top=0; |
31 | for(int i=1;i<=num;i++) |
32 | { |
33 | //出栈 |
34 | while( AA[i]<=S[top].value ) |
35 | top--; |
36 | R[i] =S[top]; |
37 | //入栈 |
38 | top++; |
39 | S[top].value=AA[i]; |
40 | S[top].idx=i; |
41 | } |
42 | top=0; |
43 | for(int i=num;i>0;i--) |
44 | { |
45 | //出栈 |
46 | while( AA[i]<=S[top].value ) |
47 | top--; |
48 | if( (top>0)&&((R[i].value ==0)||((i-R[i].idx)>(S[top].idx-i)))) |
49 | R[i]=S[top]; |
50 | //入栈 |
51 | top++; |
52 | S[top].value=AA[i]; |
53 | S[top].idx=i; |
54 | } |
55 | for(int i=1; i<num;i++) |
56 | cout<<R[i].value << " "; |
57 | cout<<R[num].value; |
58 | cout<<endl; |
59 | }//for |
60 | return 0; |
61 | } |
暴力的方式上可以进行剪枝。
1：我不用计算左和右哪个最小，我直接按照距离来，直接计算就好了，但是需要优先比较左边的。
2：如果左边或右边不存在了，那就直接在另一边找就可以了。
3：需要先排除最小值的情况，这个会方便后面的代码，如果不进行最小值判断，在计算左右满足数的时候还需要考虑输出0的情况，比较麻烦
Read full article from 九度-1422-Closest Number[数据结构] | Acm之家
