复赛4:小熊的果篮

P7912

解法一:70分

 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
#include <iostream>
using namespace std;

int a[200010],n,cnt;

int main(){
    cin>>n;
    for (int i = 1; i <=n; i++){
        cin>>a[i];
    }
    while(cnt<n){
        int flag=2;
        for(int i=1;i<=n;i++){
            if(a[i]!=-1&&a[i]!=flag){
                flag=a[i];
                a[i]=-1;
                cout<<i<<' ';
                cnt++;
            }
           
        }
         cout<<endl;
    }
    
}

解法二:80分
采用队列,以数据块为单位处理。

 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
#include <iostream>
#include <queue>
using namespace std;
struct node{
    int L,R,num;
};

int n,t,cnt;
queue<node> q;

int main(){
    int flag=2;
    cin>>n;
    for (int i = 1; i <=n; i++){
        cin>>t;
        if(t!=flag){
            q.push((node){i,i,t});
            flag=t;
        }else{
            q.back().R=i;
        }
    }
   while(!q.empty()){
    int k=q.size();
    int flag=2;
    for (int i = 1; i <=k; i++){
        if(q.front().num!=flag){
            cout<<q.front().L<<' ';
            q.front().L++;
            flag=q.front().num;
        }
        if(q.front().L<=q.front().R)
        q.push(q.front());
        q.pop();
    }
     cout<<endl;
   };
    
}

满分方法: 合并队列

 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
48
49
50
51
52
53
54
55
56
/**************************************************************** 
 * Description: 
 * Author: Alex Li
 * Date: 2023-10-16 14:55:45
 * LaLRitTime: 2023-10-17 05:44:49
****************************************************************/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

struct block{ //块
	int L, R, th;
}f, x, ad;
int n, cnt, t[200001];
queue<block> q, q2;
bool used[200001]; // 记录是否被取出
int main(){
	cin>>n;
	for (int i = 1;i <= n;i ++) cin>>t[i];
	t[n + 1] = !t[n];
	for (int i = 2, si = 1;i <= n + 1;i ++){
        // 把连续一段相同的元素合成一个块
		if (t[i] != t[i - 1]) q.push((block){si, i - 1, t[i - 1]}), si = i; 
	}
	cnt = n;
	while (cnt){
		while (q.size()){
			f = q.front();
			q.pop();
			while (used[f.L] && f.L <= f.R) f.L ++; // 如果已经被取了
			if (f.L > f.R) continue;
			cout<<f.L<<' ', cnt --;
			used[f.L] = 1; // 将块的开头元素去掉并输出
			if (f.R == f.L) continue; // 如果这个块被取完了
			f.L ++;
			q2.push(f); // 先临时存到 q2 里进行合并
		}
		cout<<endl;
		while (q2.size()){
			ad = q2.front();
			q2.pop();
			while (q2.size()){
				x = q2.front();
				if (x.th == ad.th){ // 能合并就合并
					ad.R = x.R;
					q2.pop();
				}
				else break;
			}
			q.push(ad); // 丢回队列里
		}
	}
}
Scroll to Top