众数问题

算法分析

题意描述

输入一个大小为n的有序数组，求该数组中出现次数最多的数，及其出现的次数，注：当有多个数出现次数最多时，只输出一个。

算法过程描述

假设我们先求出中位数的重数，再求出中位数往左往右延伸的距离，假设当前数组左右边界为l,r,中位数位置为mid，向左向右延伸为nl，nr。这样就把原数组分为三个子数组：[l,nl-1]，[nl,nr]，[nr+1,nr]，用第二个子数组的长度更新答案，对第一个和第三个子数组继续重复刚才的动作，为了优化搜索，当子数组大小小于当前最优解时，进行剪枝

递归方程及时间复杂度分析

分治算法解决众数问题，由代码可得递归方程为: T(n) = T(n-x) + x 其中x代表当前搜索过程中位数的重数大小，范围为1~n,计算可得代码总的时间复杂度为O(n)

流程图

算法关键代码

#include "bits/stdc++.h" using namespace std; //众数,分治,假设数组有序 int mx,ans; vector<int> a; void dfs(int l,int r) { int mid = (l+r)>>1; int ll=mid,rr=mid; while(ll-1>=l&&a[ll-1]==a[mid]) --ll; while(rr+1<=r&&a[rr+1]==a[mid]) ++rr; if(rr-ll+1>mx) mx=rr-ll+1,ans=a[mid]; if(ll-1-l+1>mx) dfs(l,ll-1); if(r-rr-1+1>mx) dfs(rr+1,r); } signed main() { freopen("input.txt", "r",stdin); freopen("output.txt","w",stdout); int n;cin>>n; a.resize(n); for(int i=0;i<n;++i) cin>>a[i]; mx = 1,ans = a[0]; dfs(0,n-1); cout<<"众数"<<ans<<" "<<"重数"<<mx<<endl; return 0; }

测试结果及分析

input.txt

8 1 2 2 2 3 4 6 8

output.txt

众数2 重数3

最小权顶点覆盖

算法分析

题意描述

（1）给定一个图，将原点集分为U，V两个集合，使得U的总权值最小，且满足对于集合V中每个顶点，集合U中都至少有一个点与他相连; （2）除此之外，如果把题意理解为，选出一个原点集的子集U，使得对于原图中任意一条边，集合U中都至少有一个点为他的顶点，又可以写出另一种代码，这里将两种题意都使用分支界限实现

算法过程描述

（1）搜索树的每个节点代表当前搜索到的集合U的状态，有三个特征值：深度，总权值，解向量，map标记。优先队列中的优先级定义为搜索树节点的代价函数。根节点中集合U为空集，初始化根节点放入优先队列中，之后开始进行广度优先搜索；对于当前搜索到的节点，如果总权值大于当前的界，进行剪枝，否则，如果为叶子节点，则更新界并返回，否则将他的两个儿子节点放入优先队列中，继续搜索过程，知道队列中不存在可以搜素的节点为止。 （2）两种题意得整体思路是一致的，只是在标记数组，子节点更新略有不同。前一种情况下map标记记录的为当前覆盖过的点，子节点更新时需要更新当前加入的点相连的每一个节点及它自身，后一种情况下map标记当前覆盖过的边，子节点更新时更新当前点相连的每一条边。

代价函数及分支限界法优化分析

因为题目要求的是最小权，需要寻找当前节点的下界，所以将代价函数定义为当前已加入集合U的总权值（假设后来的点都不会加入集合U中）。如果当前节点代价函数大于界，则进行剪枝。原搜索空间为一个子集树，最坏情况下有2^n个叶子节点。在代码中，除了使用剪枝，还使用了优先队列进行最小耗费优先搜索，大大提升了算法效率。 现通过搜索树中叶节点数目对算法优化进行分析，在原代码中加上tag标记叶节点数目，对于同一个输入样例（样例在测试结果中），测试如下： （1）未剪枝时tag值为128，即2^7，剪枝后tag值为28，相比之下优化了79% （2）未剪枝时tag值为128，即2^7，剪枝后tag值为32，相比之下优化了75%

流程图

算法关键代码

（1）

#include "bits/stdc++.h" using namespace std; #define stop system("pause") #define rpp(i,b) for(register int i=1,i##len=(int)(b);i<=i##len;++i) template <typename T> ostream& operator<<(ostream &os,const vector<T> &v) {for(auto i = begin(v);i!=end(v);i++) os<<*i<<(i==end(v)-1?"\n":" ");return os;} // ------------------------------------------------------------------------------------------------------------------------------------------------------- const int MX = 2e5 + 10; //将原点集分为U，V两个集合，使得对于V中的每个点，至少与U集合中的某个点直接相连 int w[MX]; //每个点的权 vector<int> mp[MX]; //图 class IN { public: int sumw, cnt; //目前总的权值，覆盖点数 vector<int> ans; //答案数组 map<int, int> tag; // 标记目前覆盖到的点 IN(){sumw = cnt = 0;} IN(const IN &o) { sumw = o.sumw, cnt = o.cnt, tag = o.tag; for(auto x:o.ans) ans.push_back(x); } bool operator<(IN a) const {return sumw > a.sumw;} }; signed main() { int n, m,mn = 1e9;cin >> n >> m; rpp(i,n) cin>>w[i]; rpp(_,m) { int x, y;cin >> x >> y; mp[x].push_back(y), mp[y].push_back(x); } priority_queue<IN> q; q.push(IN()); vector<int> ans; while (q.size()) { IN x = q.top();q.pop(); if (x.sumw >= mn) continue; //剪枝：当前权值已经大于ans if ((int)x.ans.size() == n) { if (x.cnt >= n && x.sumw < mn) mn = x.sumw, ans = x.ans; continue; } IN tmp = x;//不放该点 tmp.ans.push_back(0); q.push(tmp); IN tmp1 = x;//放该点 int nowid = x.ans.size() + 1; //当前放进来的是哪个点 tmp1.ans.push_back(1), tmp1.sumw += w[nowid]; //更新权值和，解向量 for(auto v:mp[nowid]) //把这个点连的点更新 { if (tmp1.tag[v] == 0) tmp1.cnt++; if (tmp1.tag[nowid] == 0) tmp1.cnt++; tmp1.tag[v] = tmp1.tag[nowid] = 1; } q.push(tmp1); } cout << mn << endl<< ans <<endl; return 0; }

（2）

#include "bits/stdc++.h" using namespace std; #define stop system("pause") #define rpp(i,b) for(register int i=1,i##len=(int)(b);i<=i##len;++i) template <typename T> ostream& operator<<(ostream &os,const vector<T> &v) {for(auto i = begin(v);i!=end(v);i++) os<<*i<<(i==end(v)-1?"\n":" ");return os;} // -------------------------------------------------------------------------------------------------------------------------------------------------------- const int MX = 2e5 + 10; //用总点权最少的一组点使原图每条边至少与子集一个点相连 int n,m,w[MX]; //点数，边数，点权 vector<int> mp[MX]; //边 class IN { public: int sumw, cnt; //目前总的权值，当前节点深度 vector<int> ans; //答案数组 map<pair<int, int>, int> tag; //覆盖到的边 IN(){sumw = cnt = 0;} IN(const IN &o) { sumw = o.sumw, cnt = o.cnt, tag = o.tag; for (auto x : o.ans) ans.push_back(x); } bool operator<(IN a) const {return sumw > a.sumw;} }; signed main() { cin >> n >> m; rpp(i, n) cin >> w[i]; rpp(_, m) { int x, y;cin >> x >> y; mp[x].push_back(y), mp[y].push_back(x); } priority_queue<IN> q; q.push(IN()); int mn = 1e9; vector<int> ans; while (q.size()) { IN x = q.top();q.pop(); if(x.sumw>=mn) continue;//剪枝：当前权值已经大于ans if ((int)x.ans.size() == n) { if (x.cnt >= m && x.sumw < mn) mn = x.sumw, ans = x.ans; continue; } //不放该点 IN tmp = x; tmp.ans.push_back(0); q.push(tmp); //放该点 IN tmp1 = x; int nowid = x.ans.size() + 1; //当前放进来的是哪个点 tmp1.ans.push_back(1), tmp1.sumw += w[nowid]; //更新权值和，答案数组 for (auto v : mp[nowid]) //把这个点加的所有边更新 { if (tmp1.tag[make_pair(nowid, v)] == 0) //这个边还没有被覆盖过 tmp1.cnt++; tmp1.tag[make_pair(nowid, v)] = tmp1.tag[make_pair(v, nowid)] = 1; } q.push(tmp1); } cout << mn << endl << ans << endl; return 0; }

测试结果及分析

输入

7 7 1 100 1 1 1 100 10 1 6 2 4 2 5 3 6 4 5 4 6 6 7

（1）输出

13 1 0 1 0 1 0 1

（2）输出

14 1 0 1 1 1 0 1