关于bitset优化贪心正确性
查看原帖
关于bitset优化贪心正确性
901086
rand_Zq楼主2024/11/1 16:58

我处理出了一个测速仪 可以让哪些车超速 记录在一个bitset中 这个bitset被称为S S[i]代表第i个测速仪可以勘测出哪些车是超速的

sort(S+1,S+m+1,cmp);
        for(int i=1;i<=m;i++){
            if(S[i].count()){
                ans++;
                auto tmp=S[i];
                for(int j=1;j<=n;j++){
                    tmp[j]=!tmp[j];
                }
                for(int j=i+1;j<=m;j++){
                    S[j]&=tmp;
                }
                sort(S+i+1,S+m+1,cmp);
            }
        }
        cout<<m-ans<<'\n';

其中cmp按bitset中1的个数排序 这通过了民间数据 他真的是对的吗?

2024/11/1 16:58
加载中...