[数据结构与算法] 一往直前：贪心法

#include<iostream>
using namespace std;
#include<algorithm>
int N,R;
#define MAX_N 1000
int X[MAX_N];
void solve(){
    sort(X,X+N);
    int i=0,ans=0;
    while(i<N){
        int s=X[i++];
        printf("s=%d\n",s);
        while(i<N&&X[i]<=s+R){
            i++;
        }
        int p=X[i-1];
        printf("p=%d\n",p);
        while(i<N&&X[i]<=p+R){
            i++;
        }
        ans++;
    }
    printf("%d\n",ans);
}
int main()
{
    scanf("%d",&N);
    scanf("%d",&R);
    for(int i=0;i<N;i++){
        scanf("%d",&X[i]);
    }
    solve();
}

输出结果：

2、区间问题

区间调度问题

问题描述

有n项工作，每项工作分别在si时间开始，在ti时间结束。对于每项工作，你都可以选择参与与否。如果选择了参与，那么自始至终都必须全程参与。此外，参与工作的时间段不能重叠（即使是开始的瞬间和结束的瞬间重叠也是不允许的）。

你的目标是参与尽可能多的工作，那么最多能参与多少项工作呢？

??限制条件

1≤N≤100000
1≤si≤ti≤109

输入样例：

n=5, s={1,2,4,6,8}, t={3,5,7,9,10}

输出样例：

3（选取工作1、3、5）

分析

这个问题通过贪心算法来求解，可以想出很多种贪心算法，如：

4、在可选的工作中、每次都选取结束时间最早的工作

所以，上述算法中，算法4是正确的，而其余两种都可以找到对应的反例。或者说，在有些情况下，他们所选取的工作并非最优。

遵循规则：在可选的工作中、每次都选取结束时间最早的工作

【证明】

结束时间越早之后，可选的工作也就越多
与其他选择方案相比，该算法的选择方案在选取了相同数量的更早开始的工作时，其最终结束时间不会比其他方案的更晚。所以，不存在选取更多的选择方案。

参考代码

#include<iostream>
using namespace std;
#include<algorithm>
#include <queue>
const int MAX_N=100000;
int N,S[MAX_N],T[MAX_N];
pair<int,int> itv[MAX_N];

void solve()
{
    // 对pair进行的是字典序比较
    // 为了让结束时间更早的工作排在前面，把T存入first，把S存入second
    for(int i=0;i<N;i++){
        itv[i].first=T[i];
        itv[i].second=S[i];
    }
    sort(itv,itv+N);
    int ans=0,t=0;
    for(int i=0;i<N;i++){
        if(t<itv[i].second){
            ans++;
            t=itv[i].first;
        }
    }
    printf("%d\n",ans);
}
int main()
{
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%d",&S[i]);
    }
    for(int i=0;i<N;i++){
        scanf("%d",&T[i]);
    }
    solve();
}

输出结果：

3、字典序最小问题

Best Cow Line

问题描述

给定长度为N的字符串S，要构造一个长度为N的字符串T。起初，T是一个空串，随后反复进行下列任一操作。

从S的头部删除一个字符，加到T的尾部
从S的尾部删除一个字符，加到T的尾部

目标是要构造字典序尽可能小的字符串T。

?? 限制条件

1≤N≤2000
字符串S只包含大写英文字母

输入样例：

N=6

S="ABCDBCB"

输出样例：

ABCDBCB（如下图所示进行操作）

分析

字典序是指从前到后比较两个字符串大小的方法。首先比较第1个字符，如果不同则第1个字符较小的字符串更小，如果相同则继续比较第2个字符......如此继续，来比较整个字符串的大小

字符串比较类的问题经常能用得上贪心算法。

从字典序的性质上看，无论T的末尾有多大，只要前面部分的较小就可以，所以我们可能得到如下算法：

不断取S的开头和末尾中较小的一个字符放到T的末尾

这个算法已经接近正确了，只是针对S的开头和末尾字符相同的情形还没有定义。在这种情形下，因为我们希望能够尽早使用更小的字符，所就要比较下一个字符的大小。下一个字符也有可能相同，因此就有如下算法：

遵循规则：

按照字典序比较 S和将S反转后的字符串S
如果S较小，就从S的开头取出一个字符，追加到T的末尾

如果S较小，就从S的开头取出一个字符，追加到T的末尾

（如果相同则取哪个都可以）

参考代码

#include<iostream>
using namespace std;
#include<algorithm>
#include<cstdio>
#define max_N 2000
int N;
char S[max_N+1];
void solve()
{
    int a=0;
    int b=N-1;
    while(a<=b){
        // 将从左起和从右起的字符串比较
        bool left=false;
        for(int i=0;a+i<=b;i++){ // 考虑了左起和右起字符相同的情况
            if(S[a+i]<S[b-i]){
                left=true;
                break;
            }
            else if(S[a+i]>S[b-i]){
                left=false;
                break;
            }
        }
        if(left){
            putchar(S[a++]);
        }
        else{
            putchar(S[b--]);
        }
    }
    putchar('\n');
}
int main()
{
    scanf("%d",&N);
    scanf("%s",S);
    solve();
}

输出结果：

4、Saruman's Army

问题描述

直线上有N个点。点i的位置是Xi。从这N个点中选择若干个，给它们加上标记。对每一个点，其距离为R以内的区域里必须有带标记的点（自己本身带有标记的点，可以认为与其距离为0的地方有一个带标记的点）。在满足这个条件的情况下，希望能为尽可能少的点添加标记。请问至少要有多少点被加上标记？

?? 限制条件

1≤N≤1000
0≤R≤1000

0≤Xi≤1000

输入样例：

N=6

R=10

X={1,7,15,20,30,50}

输出样例：

分析

我们从最左边开始考虑。对于这个点，到距其R以内的区域内必须要有带有标记的点。（此点位于最左边，所以显然）带有标记的这个点一定在此点最右侧（包含这个点自身）。

于是，究竟要给哪个点加上标记呢？答案应该是从最左边的点开始，距离为R以内的最远的点。因为更左的区域没有覆盖的意义，所以应该尽可能覆盖更靠右的点。

遵循规则：

如上图所示，加上了第一个标记后，剩下部分也用同样的办法处理。对于添加了符号的点右侧相距超过R的下一个点，采用同样的方法找到其右侧R距离以内最远的点添加标记。在所有的点都被覆盖之前不断地重复这一过程。

参考代码

#include<iostream>
using namespace std;
#define max_N 1000
int N,R;
int X[max_N];
void solve()
{
    sort(X,X+N); // 输入的数据可能并没有按顺序排列
    int i=0,ans=0;
    while(i<N){
        // s是没有被覆盖的最左的点的位置
        int s=X[i++];
        // 一直向右前进直到距s的距离大于R的点
        while(i<N&&X[i]<=s+R){
            i++;
        }
        // p是新加上标记的点的位置
        int p=X[i-1];
        // 一直向右前进直到距p的距离大于R的点
        while(i<N&&X[i]<=p+R){
            i++;
        }
        ans++;
    }
    printf("%d\n",ans);
}
int main()
{
    scanf("%d",&N);
    scanf("%d",&R);
    for(int i=0;i<N;i++){
        scanf("%d",&X[i]);
    }
    solve();
}

输出结果：

其他

为帮助理解，在此多测了一组数据，帮助理解

5、Fence Repair

问题描述

?? 限制条件

1≤N≤20000

1≤Li≤20000

输入样例：

N=3, L={8,5,8}

输出样例：

分析

切割的问题可以参见下图的二叉树来描述。

这里每一个叶子结点就对应了切割出的一块块木板、叶子节点的深度就对应了为了得到对应木板所需的切割次数，开销的合计就是各叶子节点的?木板的长度×节点的深度?的总和。例如，上图示例的全部开销就可以这样计算：

于是，此时的最佳切割方法首先应该具有如下性质：

最短的板与次短的板的节点应当是兄弟节点

对于最优解来讲，最短的板应当是深度最大的叶子节点之一。所以与这个叶子节点同一深度的兄弟节点一定存在，并且由于同样是最深的叶子节点，所以应该对应于次短的板。

不妨将Li按照大小顺序排列，那么最短的板应该是L1而次短的则是L2。如果它们在二叉树中是兄弟节点，就意味着它们是从一块长度为（L1+L2）的板切割得来的。由于切割顺序是自由的，不妨当作是最后被切割。这样一来，在这次切割前就有

这样的 N-1 块木板存在。与以上讨论的方式相同，递归地将这N-1块木板的问题求解，就可以求出整个问题的答案了。这实现的话，虽然复杂度是O(N2)，对于题目的输入规模来说，已经足以在时间限制内通过了。

遵循规则：每次找出最小的两块板，作为一块最后被切割的板，记录下两块板长度之和，如此递归

参考代码

#include<iostream>
using namespace std;
typedef long long ll;
#define max_N 20000
int N,L[max_N];
void solve()
{
    ll ans =0;
    // 直到计算到木板为1块止
    while(N>1){
        // 求出最短的板mii1和次短的板mii2
        int mii1=0,mii2=1;
        if(L[mii1]>L[mii2]){
            swap(mii1,mii2); // L[0]、L[1]中最小的赋值为幂mii1
        }
        for(int i=2;i<N;i++){ // 遍历数组L，确保最短的木板赋值为mii1，次短的为mii2
            if(L[i]<L[mii1]){
                mii2=mii1;
                mii1=i;
            }
            else if(L[i]<L[mii2]){
                mii2=i;
            }
        }
        // 将两块板拼合
        int t=L[mii1]+L[mii2];
        ans+=t;
        if(mii1==N-1){  // 确保mii1不等于N-1,否则L[mii1]和L[mii2]记录的值均为L[N-1]
            swap(mii1,mii2);
        }
        L[mii1]=t; // L[mii1]的值为合并后木板的长
        L[mii2]=L[N-1];  // mii2保存将要被删掉的L[N-1]的值
        N--; // 因为最短和最短的已经合并，数组元素应当少一个
    }
    printf("%lld\n",ans);
}
int main()
{
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%d",&L[i]);
    }
    solve();
}

输出结果：

6、霍夫曼（Huffman）编码

字符用0和1组成的序列对应起来后，一篇文章可以用一连串0和1的序列来表达。一般的字符编码就是这些对应关系当中的一种。但是，不同的字符在文章中出现的频率会有所不同，由此将频率比较高的字符，对应到比较短的序列，而将频率比较低的字符对应到较长的序列。这样文章可以用更短的序列来表达。这就是常见的文本压缩方法。

举例

假设某文件中只有6中字符：a,b,c,d,e,f 可以用3个二进制来表示，如下图所示：（频率的单位均为“千次”）

步骤：

1、

2、

3、

4、

5、

6、根据左0右1最终得到：

此外不难发现每个字符编码开头都是不相同的，所以很容易根据编码，辨别出分别代表哪些字符，如：

010011111011100101101100111 代表字符串

7、Prim算法求最小生成树

概念：

连通图的生成树：包括所有顶点的连通无环子图
数的权重：所有边的权总和

连通图带权最小生成树：最小的总权重生成树

遵循规则：Prim算法通过一系列不断扩张的子树构造一颗最小生成树

从图中任意选择一个顶点，作为初始树
以贪心的方式扩张当前的生成树，即把不在树中的顶点添加到树中

当图中的所有顶点都包含在树中时，算法停止

扩张原则：不在树中的顶点，以权重最小的边和树中的顶点相连

说明：Prim算法每个顶点只选择一次，包括的边的条数为边数-1 ，所以隐含了不可能生成环

分析

举例

步骤：

参考代码

#include<iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
const int max_V = 10000;
int cost[max_V][max_V]; //cost[u][v]表示边e=(u,v)的权值（不存在的情况设为INF）
int mincost[max_V]; // 从集合x出发的边到每个顶点的最小权值
bool used [max_V]; // 顶点i是否包含在集合X中
int V; // 顶点数
int prim()
{
    for(int i=0;i<V;i++){  // 初始化
        mincost[i]=INF;
        used[i]=false;
    }
    mincost[0]=0;
    int res =0;
    while(true){  //选取第V-1个顶点为起点
        int v=-1;
        // 从不属于X的顶点中选取从x到其权值最小的顶点
        for(int u=0;u<V;u++){
            if(!used[u]&&(v==-1||mincost[u]<mincost[v])){
                v=u;
            }
        }
        if(v==-1){
            break;
        }
        used[v]=true; // 把顶点v加到x
        res+=mincost[v];  // 把边的长度加到结果里
        for(int u=0;u<V;u++){
            mincost[u]=min(mincost[u],cost[v][u]);
        }
    }
    return res;
}
int main()
{
    scanf("%d",&V);
    for(int i=0;i<V;i++){  
        for(int j=0;j<V;j++){
            scanf("%d",&cost[i][j]);
        }
    }
    printf("%d\n",prim());
}

输出结果：

样例1：（此处以1000代表无穷大）

样例2：

8、Kruskal算法求最小生成树

Prim算法：贪婪地包含离树中顶点最近的顶点
Kruskal算法：贪婪地包含最小边

分析

步骤：

注意：

该算法看起来比Prim算法容易，但更难执行，需要检查是否产生回路
回路检查：增加的边连接了两个顶点，而这两个顶点是否处于同一个集合中

接下来让我们介绍如何产生圈（回路），假设现在要把连接顶点u和顶点v的边e加入生成树中。如果加入之前u和v不在同一个连通分量里，那么加入e也不会产生圈。反之，如果u和v在同一个连通分量里，那么一定会产生圈。可以使用并查集高效地判断是否属于同一个连通分量。

Kruskal算法在边的排序上最费时，算法的复杂度是O(|E|long|V|)

参考代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100;
int nodeset[N];
int n, m; // 顶点数和边数
struct Edge {
    int u;
    int v;
    int w;
}e[N*N];
bool comp(Edge x, Edge y) {
    return x.w < y.w;
}
void Init(int n)  // 并查集的初始化
{
    for(int i = 1; i <= n; i++)
        nodeset[i] = i;
}
int Merge(int a, int b)
{
    int p = nodeset[a];
    int q = nodeset[b];
    if(p==q) return 0;
    for(int i=1;i<=n;i++)//检查所有结点，把集合号是q的改为p
    {
      if(nodeset[i]==q)
        nodeset[i] = p;//a的集合号赋值给b集合号
    }
    return 1;
}
int Kruskal(int n)
{
    int ans = 0;
    for(int i=0;i<m;i++)
        if(Merge(e[i].u, e[i].v))
        {
            ans += e[i].w;
            n--;
            if(n==1)
                return ans;
        }
    return 0;
}
int main() {
        cout <<"输入结点数n和边数m:"<<endl;
        cin >> n >> m;
        Init(n);  //并查集的初始化
        cout <<"输入结点数u,v和边值w:"<<endl;
        for(int i=1;i<=m;i++)
            cin >> e[i].u>> e[i].v >>e[i].w;
        sort(e, e+m, comp);  // 按照Edge.w的顺序从小到大排序
        int ans = Kruskal(n);
        cout << "最小的花费是：" << ans << endl;
    return 0;
}

输出结果：（这里用1-6分别代表a-f)

9、Dijkstra算法——单源点最短路径

Dijkstra算法：单起点最短路径问题（单源点、固定起点）, 实际生成的是最小生成树
Floyd算法：完全最短路路径问题（动态规划）

单源点最短路径问题：给出加权连通图G, 求从一个顶点到其他所有顶点的最短路径

分析

Dijkstra算法：

与Prim算法相似，用一种不同的方式计算权值
没有出现在集合中的顶点，用最小的代价值，找到顶点u。dv+w(v,u)，v是最接近起点的顶点，dv是从原点到v最短的距离长度，w(v,u)是v到u这条边的长度。

参考代码

#include <iostream>
#include<cstring>
#include<stack>
using namespace std;
const int MaxVnum=100; // 顶点的个数可修改
const int INF=1e7; // 无穷大10000000
int dist[MaxVnum],p[MaxVnum];//最短距离和前驱数组
bool flag[MaxVnum]; //如果s[i]等于true，说明顶点i已经加入到集合S;否则顶点i属于集合V-S

typedef string VexType;  //顶点的数据类型，根据需要定义
typedef int EdgeType;  //边上权值的数据类型，若不带权值的图，则为0或1
typedef struct{
  VexType Vex[MaxVnum];
  EdgeType Edge[MaxVnum][MaxVnum];
  int vexnum,edgenum; //顶点数，边数
}AMGragh;

int locatevex(AMGragh G,VexType x)
{
    for(int i=0;i<G.vexnum;i++)//查找顶点信息的下标
       if(x==G.Vex[i])
        return i;
    return -1;//没找到
}

void CreateAMGraph(AMGragh &G)
{
    int i,j,w;
    VexType u,v;
    cout << "请输入顶点数："<<endl;
    cin>>G.vexnum;
    cout << "请输入边数:"<<endl;
    cin>>G.edgenum;
    cout << "请输入顶点信息:"<<endl;
    for(int i=0;i<G.vexnum;i++)//输入顶点信息，存入顶点信息数组
        cin>>G.Vex[i];
    for(int i=0;i<G.vexnum;i++)//初始化邻接矩阵为无穷大
      for(int j=0;j<G.vexnum;j++)
         G.Edge[i][j]=INF;
    cout << "请输入每条边依附的两个顶点及权值："<<endl;
    while(G.edgenum--)
    {
       cin>>u>>v>>w;
       i=locatevex(G,u);//查找顶点u的存储下标
       j=locatevex(G,v);//查找顶点v的存储下标
        if(i!=-1&&j!=-1){
            G.Edge[i][j]=w; //有向图邻接矩阵
            G.Edge[j][i]=w; //若为无向图，则需要这一步
        }
       else
       {
           cout << "输入顶点信息错！请重新输入！"<<endl;
           G.edgenum++;//本次输入不算
       }
    }
}

void Dijkstra(AMGragh G,int u)
{
   for(int i=0;i<G.vexnum;i++)
    {
     dist[i]=G.Edge[u][i]; //初始化源点u到其他各个顶点的最短路径长度
     flag[i]=false;
     if(dist[i]==INF)
       p[i]=-1; //源点u到该顶点的路径长度为无穷大，说明顶点i与源点u不相邻
     else
       p[i]=u; //说明顶点i与源点u相邻，设置顶点i的前驱p[i]=u
     }
    dist[u]=0;
    flag[u]=true;   //初始时，集合S中只有一个元素：源点u
    for(int i=0;i<G.vexnum; i++)
     {
        int temp=INF,t=u;
        for(int j=0;j<G.vexnum; j++) //在集合V-S中寻找距离源点u最近的顶点t
          if(!flag[j]&&dist[j]<temp)
          {
            t=j;
            temp=dist[j];
          }
        if(t==u) return ; //找不到t，跳出循环
        flag[t]= true;  //否则，将t加入集合
        for(int j=0;j<G.vexnum;j++)//更新与t相邻接的顶点到源点u的距离
          if(!flag[j]&&G.Edge[t][j]<INF)
            if(dist[j]>(dist[t]+G.Edge[t][j]))
             {
               dist[j]=dist[t]+G.Edge[t][j] ;
               p[j]=t ;
             }
       }
}
void findpath(AMGragh G,VexType u)
{
  int x;
  stack<int>S;
  cout<<endl;
  for(int i=0;i<G.vexnum;i++)
  {
    x=p[i];
    if(x==-1&&u!=G.Vex[i])
    {
        cout<<"源点到其它各顶点最短路径为："<<u<<"--"<<G.Vex[i]<<"    sorry,无路可达"<<endl;
        continue;
    }
    while(x!=-1)
    {
      S.push(x);
      x=p[x];
    }
    cout<<"源点到其它各顶点最短路径为：";
    while(!S.empty())
    {
      cout<<G.Vex[S.top()]<<"--";
      S.pop();
    }
    cout<<G.Vex[i]<<"    最短距离为："<<dist[i]<<endl;
  }
}

int main()
{
        AMGragh G;
        int st;
        VexType u;
        CreateAMGraph(G);
        cout <<"请输入源点的信息:"<<endl;
        cin>>u;
        st=locatevex(G,u);//查找源点u的存储下标
        Dijkstra(G,st);
        cout <<"源点位置:"<<u<<endl;
        for(int i=0;i<G.vexnum;i++)
        {
             cout <<"源点"<<u<<" - "<<G.Vex[i];
             if(dist[i]==INF)
               cout << " sorry,无路可达"<<endl;
             else
               cout << " 最短距离为:"<<dist[i]<<endl;
         }

         findpath(G,u);
         return 0;
}

输出结果：