社区讨论

有一个疑问

P7912[CSP-J 2021] 小熊的果篮参与者 4已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mhjhpuy1
此快照首次捕获于
2025/11/04 02:45
4 个月前
此快照最后确认于
2025/11/04 02:45
4 个月前
查看原帖
这个是STL写的链表的做法,四个点TLE,比暴力还烂
CPP
#include <bits/stdc++.h>
using namespace std;

struct node {
    int a;
    int no;
};

list<node> s;

int main() {
    std::ios::sync_with_stdio(false);
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int b;
        cin >> b;
        s.push_back(node{b, i}); initialize each node
    }

    while (!s.empty()) {
        int now = -1;
        list<node>::iterator it;

        for (it = s.begin(); it != s.end(); ++it) {
            if (it->a != now) {
                cout << it->no << ' ';
                now = it->a;
                it->a = -2; 
            }
        }
        cout << endl;

        s.remove_if([](const node& x) { return x.a == -2; });
    }

    return 0;
}
这个是手写的链表做的,内外循环都差不多,但是这个就AC
CPP
#include <bits/stdc++.h>
using namespace std;
struct node{
	int pre;
	int nxt;
};

void solve(){
	int n;
	cin>>n;
	vector<int> a(n+2);
	vector<node> lst(n+2);
	vector<int> now;

	a[0]=2;
	a[n+1]=2;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]!=a[i-1]){
			now.push_back(i);
		}
		lst[i].pre=i-1;
		lst[i].nxt=i+1;
	}
	lst[0].nxt=1;
	 while(lst[0].nxt <= n){
	 	vector<int> tmp;
	 	for(int x : now){
		
		cout<<x<<' ';
		lst[lst[x].nxt].pre=lst[x].pre;
		lst[lst[x].pre].nxt=lst[x].nxt;
		if(a[lst[x].pre] != a[lst[x].nxt] && a[x] == a[lst[x].nxt]){ 
		 tmp.push_back(lst[x].nxt); 
            }
	}
	cout<<endl;
	now=tmp;
}
	 
	
	
}
int main(){
	solve();
	return 0;
}
我想问一下这个是为什么?

回复

4 条回复,欢迎继续交流。

正在加载回复...