众数问题
算法分析
题意描述
输入一个大小为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