这是本系列的第二篇文章，旨在记录我学习C++历程中所有的感想和感悟。

2.1 最多水容器

题目信息

题目描述：

给定一个数组, 每个数值代表柱子的高度, 那么求出这些柱子最多可以装多少水. 水的体积由较短的长度乘以两个柱子的距离.

上面的图的输入为 [1,8,6,2,5,4,8,3,7]. 蓝色区域最可以装水为49.

输入

第一行输入一个数字N表示容器个数。第二行输入N个使用空格间隔的证书，表示容器高度。

输出

输出一个数字表示最多装水量。

样例输入

9
1 8 6 2 5 4 8 3 7

样例输出

49

数据范围

题目分析

方法一：暴力模拟

直接暴力选取所有情况然后比较出最大值，时间复杂度

#include<bits/stdc++.h>
using namespace std;
int a[11];
int water(int *a,int first,int last)
{
    return min(a[first],a[last])*(-first+last);
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)
    {
        ans=max(ans,water(a,i,j));
    }
    cout<<ans<<endl;
    system("pause");
    return 0;
}

方法二：尺取法扫描

对于一个木桶来说，决定其最大盛水量的往往是小的木桶板，而理想上扩大容量就需要将小的变成大的。 对于木桶，在两端设立两个指针first和last，计算区间内木桶的容量，再将木板长度较小的指针向里移动，逐次比较直至指针撞在一起，结束比较并输出结果。 此方法采用线性扫描的方式，几何倍数的缩小时间复杂度至.

#include<bits/stdc++.h>
using namespace std;
int a[11];
int water(int *a,int first,int last)
{
    return min(a[first],a[last])*(-first+last);
}
int search(int *a,int first,int last)
{
    int maxn=-1;
    while(first!=last)
    {
        maxn=max(maxn,water(a,first,last));
        a[first]>=a[last]? last--:first++;
    }
    return maxn;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    cout<<search(a,1,n)<<endl;
    system("pause");
    return 0;

}

2.2 区间和统计

题目信息

题目描述：

给定一个包含个元素的数组,数组中元素保证 。在数组中,从到的所有数叫做数组的一个子区间,你需要求出,所有子区间中,和为的区间一共有多少个。

输入

第一行包含一个整数表示样例个数。

对于每一个样例,第一行输入两个数字,,$ pn$表示数组的长度, 代表区间和。

第二行包含个数字表示数组的元素。

输出

对于每一个样例,输出一个数字表示和为的子区间个数。

样例输入

1
5 8
4 4 4 4 4

样例输出

4

数据范围

所有的均为整数。

保证

题目分析

方法：数组前缀和

和为的子区间的个数，如果采用暴力必定超时，此时数组前缀和将大幅度降低算法的时间复杂度。

前缀和的精髓在于，将双端点不确定的闭区间转化成了单端点不确定的两个区间和,这样就可以通过的时间复杂度来得到某个区间的子段和。

#include <bits/stdc++.h>
using namespace std;
int a[1001];
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin>>n;
        int k;
        cin>>k;
        int ans=0;
        for (int i = 1; i <= n; i++)
        {
            cin>>a[i];
            a[i]+=a[i-1];
        }
        for(int i=0;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        if(a[j]-a[i]==k)ans++;
        cout<<ans<<endl;

    }
    system("pause");
    return 0;
}

2.3 子矩阵求和

题目信息

题目描述：

给定一个M行N列的矩阵，要求你求得子矩阵, 的内所有元素的和。其中和是子矩阵的两个顶点。

输入

第一行输入包括三个数字。

接下来行每行个整数，表示需要处理的矩阵。

接下来行每行四个整数，表示子矩阵的方位。

输出

对于每一次询问，输出子矩阵内所有元素的和。

样例输入

4 3 2
1 2 3
4 5 6
7 8 9
10 11 12
0 0 3 2
0 0 1 1

样例输出

78
12

数据范围

题目分析

方法：二维数组前缀和

原理同上，公式有所变化。

设二元函数表示从元素到元素的全部元素和，则有：

对于矩阵

其元素和可以表示为

注意：对于此题，元素的对应坐标为.而且，和大小要排对

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull a[1001][1001];
int main()
{
    ull m,n,q;
    cin>>m>>n>>q;
    for(ull i=1;i<=m;i++)
        for(ull j=1;j<=n;j++) 
            {
                cin>>a[i][j];
                a[i][j]+=(a[i-1][j]+a[i][j-1]-a[i-1][j-1]);
            }
    while(q--)
    {
        ull x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
       if(x1>x2)swap(x1,x2);//
       if(y1>y2)swap(y1,y2);//
        cout<<a[x2+1][y2+1]+a[x1][y1]-a[x1][y2+1]-a[x2+1][y1]<<endl;

    }
    system("pause");
    return 0;
}

2.4 选择排序

题目信息

题目描述：

给你一个序列，按照从小到大的顺序重新排列，要求使用选择排序

输入

第一行是一个正整数，代表测试样例的个数

对于每组测试样例，输入一行数字，第一个数字，代表这组样例中数字的个数，接下来的个数字代表所给序列

输出

对于每组输出样例，输出一行，输出按照从小到大顺序排列的结果

样例输入

3
2
2 1
5
9 5 1 4 3
6
2 3 8 1 5 6

样例输出

1 2
1 3 4 5 9
1 2 3 5 6 8

数据范围

正常范围之内

题目分析

虽然说本题目是标定了为选择排序，但在此处将系统的罗列最常见的九大种排序算法以及相应的细节分析。

方法一：冒泡排序

平均时间复杂度：

最佳时间复杂度：

最坏时间复杂度：

空间复杂度：

稳定性：稳定

冒泡排序，不多解释

void bubbles(int *a,int n)//从小到大
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n-i;j++)
        {
            if(a[j]>a[j+1])swap(a[j],a[j+1]);
        }
    }
}

方法二：选择排序

平均时间复杂度：

最佳时间复杂度：

最坏时间复杂度：

空间复杂度：

稳定性：不稳定

选择排序，即从左到右，设定指针指向目标基准，遍历后面的所有元素，如果有比基准值小的则更新基准值。遍历结束后，将更新完的基准值和互换位置。

void selectsort(int *a, int n)
{
    int min;
    for (int i = 1; i <= n; i++)
    {
        min = i;
        for (int j=i+1;j<=n;j++)
        {
            if(a[min]>a[j])min=j;
        }
        if(min!=i)swap(a[min],a[i]);
    }
}

方法三：插入排序

平均时间复杂度：

最佳时间复杂度：

最坏时间复杂度：

空间复杂度：

稳定性：稳定

插入排序，即扑克牌排序法，左手上的握着的牌全部是排好顺序的（从小到大），桌子上的牌是初始的乱序状态。每次从桌子上摸一张牌放到最后面，然后和前面的比较，如果比前面的小就插入到前面；重复，直到前面的牌不比目标牌大，停止交换。宏观上，就把这个牌插入到了预定的位置，所以叫插入排序。对应到数组，就是选定目标为摸到的牌，到为左手上的有序牌，执行上述操作。

void insertsort(int *a,int n)
{
    for(int i=2;i<=n;i++)
    {
        for(int j=i-1;j>=1;j--)
        {
            if(a[j]>a[j+1])swap(a[j],a[j+1]);
            else break;
        }
    }
    return;
}

方法四：希尔排序

平均时间复杂度：（Sedgewick法）

最佳时间复杂度：

最坏时间复杂度：（原初希尔排序算法）

空间复杂度：

稳定性：不稳定

希尔排序是对插入排序的升级操作，拒绝了挨个位置的询问交换，变成了按固定区间距离差的询问转换。在完成一次遍历后，通过类似二分的方法降低空间距离差，重复距离排序，直至最后步长降到1.

希尔排序最不稳定的原因之一就是对于基础步长R的选择，R的数值会很大程度上影响希尔排序的速度，而且相等元素也可能交换位置。目前已知的希尔排序最速R是由Sedgewick提出的，增量公式为

或

void shell_sort(int *a,int n)
{
    int R={0,929,505,209,109,41,19,5,1,0}
    int i=-1;
    for(int j=1;j<=8;j++)
        if(n>=R[j]){i=j;break;}
    if(i==-1)return;//如果输入的n不合法，结束运算。
    for(;i<=8;i++)//依次带入区间基准R
    {
        for (int j=R[i]+1; j<=length;j++) //选定比较者
        {
            for (int o=j;o>=R[i]+1&&a[o]<array[o-R[i]]; o-=R[i]) //如果发生交换，将会影响整一组的顺序，需要重新全部洗牌。
            {
                swap(a[o], array[o-R[i]]);
            }
        }
    }
    return;
}

方法五：归并排序

平均时间复杂度：

最佳时间复杂度：

最坏时间复杂度：

空间复杂度：

稳定性：稳定

归并排序，采用二分+合并思想，现将总序列分为两个序列，然后分别递归调用使之成为两段有序序列，然后合并。

一共有两种写法，一种是自上而下递归调用，一种是自下而上迭代。这里只讨论自上而下递归的方法

void mergesort_build(int *a,int first,int last)
{
    int mid=(first+last)>>1;
    int *ans=new int[last-first+2];
    int i=first,j=mid+1,k=1;
    while(i<=mid&&j<=last)//移动插入合并序列
    {
        if(a[i]>=a[j])
        ans[k++]=a[j++];
        else
        ans[k++]=a[i++];
    }
    while(i<=mid)//有剩余直接补到队尾
    {
        ans[k++]=a[i++];
    }
    while(j<=last)//有剩余直接补到队尾
    {
        ans[k++]=a[j++];
    }
    for(int s=first,k=1;s<=last;s++,k++)//返还序列
    {
        a[s]=ans[k];
    }
    delete[] ans;
    return;
}
void mergesort(int *a,int first,int last)
{
    if(first!=last)
    {
        int mid=(first+last)>>1;
        mergesort(a,first,mid);
        mergesort(a,1+mid,last);
    }
    mergesort_build(a,first,last);
    return;
}

方法六：快速排序

平均时间复杂度：

最佳时间复杂度：

最坏时间复杂度：

空间复杂度：

稳定性：不稳定

快速排序，相较于其他算法的速度会略快一些，但是一些时候仍然会出现最坏的时空复杂度,属于是赔本买卖了。

快速排序的思路是，选定第一个数为基准数字，先从右向左找到第一个不大于基准值的数字位置，再从左到右找到第一个不小于基准值的数字，二者交换位置。重复，直至i和j重合。

注意！顺序不能反，必须先从右向左在从左向右，否则会出错；而如果选定中间值为基准值就没有这个限制。

第一个为基准

void quicksort(int a[],int begin,int end)
{
    if(begin>end)return;
    int i=begin;
    int j=end;
    while(i!=j)
    {
        while(j>i&&a[j]>=a[begin])j--;//顺序千万不能倒了
        while(j>i&&a[i]<a[begin])i++;
        if(j>i)swap(a,j,i);
    }
    swap(a,begin,i);
    quicksort(a,begin,i-1);
    quicksort(a,i+1,end);
}

中间值为基准

void quicksort(int l,int r)
{
    int mid=a[(l+r)/2];
    int i=l,j=r;
    do{
        while(a[i]<mid) i++;
        while(a[j]>mid) j--;
        if(i<=j)
        {
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }while(i<=j);
    if(l<j) quicksort(l,j);
    if(i<r) quicksort(i,r);
}

方法七：堆排序

平均时间复杂度：

最佳时间复杂度：

最坏时间复杂度：

空间复杂度：

稳定性：不稳定

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念的选择排序，通过构造大顶堆/小顶堆来完成元素排序。

以构造大顶堆为例分析堆得构造原理。

构造大顶堆，需要找到最后一个非叶子节点以此从右至左、从下至上完成堆的索引与组建。对于数组组建而成的堆，它的最后一个非叶子节点的位置是的数组下标；它的全部非叶子节点下标则为$0,1,,-1 a[0]n-1$个数组成的大顶堆，循环往复，直至所有n个堆完成遍历。

#include<bits/stdc++.h>
using namespace std;
void swap(int *a,int m,int n)
{
    int arr=a[m];
    a[m]=a[n];
    a[n]=arr;
    return;
}
void buildheap(int *a,int n)//建堆，元素个数为n
{
    for(int target=n/2-1;target>=0;target--)//最小非叶子节点
    {
        int parent=target;
        int child=2*parent+1;
        while(child<n)
        {
            if(child+1<n&&a[child]<a[child+1])child++;
            if(a[child]>a[parent])
            {
                swap(a,child,parent);
                parent=child;
                child=child*2+1;
                continue;
            }//转移至更改的节点分析该节点以下的数据
            break;//否则直接退出，不用再管下面
        }
    }

}
void heapsort(int *a,int n)
{
    for(int i=n;i>=1;i--)
    {
        buildheap(a,i);
        swap(a,0,i-1);
    }
    return;

}
int main()
{
    int a[10]={0,1,8,7,4,5,3,2,6,9};
    heapsort(a,10);//堆排序从a[0]开始，较之前从a[1]开始不同。
    system("pause");
    return 0;
}

方法八：计数排序（桶排序）

平均时间复杂度：

最佳时间复杂度：

最坏时间复杂度：

空间复杂度：

稳定性：稳定

计数排序，或者称为最小桶排序，是将数组的元素个数放到以其元素为下标的数组内，并按顺序输出的算法。

void countsort(int *a,int n)
{
    int maxn=-1e6;
    for(int i=1;i<=n;i++)
    {
        maxn=max(maxn,a[i]);
    }
    int *p=new int[maxn+1];
    memset(p,0,sizeof(p));
    for(int i=1;i<=n;i++)
    {
        p[a[i]]++;
    }
    for(int i=1;i<=n;i++)
    {
        while(p[i])
        {
            cout<<i<<" ";
            p[i]--;
        }
    }
    cout<<endl;
    return;
}

方法九：基数排序

平均时间复杂度：

最佳时间复杂度：

最坏时间复杂度：

空间复杂度：

稳定性：稳定

基数排序是桶排序的升级版，相较而言节省了一定的数组空间，但随之的是时间成本单位增加。 基数排序将桶固定为了某一位数字，按照个位，十位，······的顺序依次桶排序后叠放，即可得出结果。

int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
    int maxData = data[0];              ///< 最大数
    /// 先求出最大数，再求其位数。
    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >= p)
    {
        maxData /= 10;
        ++d;
    }
    return d;

}
void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //计数器数据转换为临时数组的存放位置区间
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}

题目代码

#include <bits/stdc++.h>
using namespace std;
void selectsort(int *a, int n)//选择排序
{
    int min;
    for (int i = 1; i <= n; i++)
    {
        min = i;
        for (int j=i+1;j<=n;j++)
        {
            if(a[min]>a[j])min=j;//最小基准值更换
        }
        if(min!=i)swap(a[min],a[i]);//最小值交换
    }
}
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int s;
        cin >> s;
        int *a = new int[s + 1];
        for (int i = 1; i <= s; i++)
            cin >> a[i];
        selectsort(a,s);
        for(int i=1;i<=s;i++)
        cout<<a[i]<<" ";
        cout<<endl;
        delete[] a;

    }
    system("pause");
    return 0;
}

2.5 前m大的数

题目信息

题目描述：

给定一个包含个正整数的序列，每个数不超过，对它们两两相加得到的 个和，求出其中前大的数并按从大到小的顺序排列。

输入

输入可能包含多组数据，其中每组数据包括两行：

第一行两个数和，

第二行个数，表示该序列。

输出

对于输入的每组数据，输出个数，表示结果。输出应当按照从大到小的顺序排列。

样例输入

4 4
1 2 3 4
4 5
5 3 6 4

样例输出

7 6 5 5
11 10 9 9 8

数据范围

正常范围之内

题目分析

暴力模拟，将得到的结果存放到数组b当中，然后排序输出。

有一个小的问题，鉴于元素过多，普通二分和快速排序均会产生超时，借助STL的sort函数解决大规模数据排序是一个必要的手段，毕竟C++专家们写出来的最快的排序算法还是一个不赖的东西。

#include<bits/stdc++.h>
using namespace std;
void quicksort(int *a,int first,int last)
{
    int mid=a[(first+last)/2];
    int i=first,j=last;
    do
    {
        while(a[i]>mid)i++;
        while(a[j]<mid)j--;
        if(i<=j)
        {
            swap(a[i],a[j]);
            i++;
            j--;
        }
        if(first<j)quicksort(a,first,j);
        if(last>i)quicksort(a,i,last);

    }while(i<=j);
}
bool compare(int a,int b)
{
    return a>b;
}
 int a[3005],b[10000000];
int main()
{
    int n,q;
   
    while(cin>>n>>q)
    {
        for(int i=1;i<=n;i++)
        cin>>a[i];
        int s=1;
        for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        b[s++]=a[i]+a[j];
        //quicksort(b,1,s-1);
        sort(b+1,b+s,compare);
        for(int i=1;i<=q;i++)cout<<b[i]<<" ";
        cout<<endl;
    }
    system("pause");
    return 0;
}

2.6 Greed

题目信息

题目大意：

有个桶，每个桶的容积为,装有的水。请问能否实现将这些水全部导入两个容器内。

输入

数据包括三行：

第一行桶的个数。

第二行个数，表示第个桶装了升水。

第三行个数，表示第个桶容积。

输出

满足要求，输出YES，否则NO.

样例输入

2
3 5
3 6

样例输出

YES

数据范围

题目分析

数据过大，不好完成排序(数组存放的极限是)。所以进行逐个比较并且记录从到的区间内的最大与第二大值。然后对水容量叠加后比较，注意开ull。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int main()
{
    ull n;
    cin>>n;
    ull sum=0;
    for(ull i=1;i<=n;i++)
    {
        ull s;
        cin>>s;
        sum+=s;
    }
    ull max1=0,max2=-1;
    for(ull i=1;i<=n;i++)//记录第一大和第二大
    {
        ull s;
        cin>>s;
        if(s>max1){max2=max1;max1=s;}
        if(s<max1)
        {
            if(s<max2)max2=s;
        }
    }
    if(max1+max2>=sum)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    system("pause");
    return 0;
}

2.7 珠心算测验

题目信息

题目大意：

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？

输入

共两行，第一行包含一个整数，表示测试题中给出的正整数个数。 第二行有个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。 输出

一个整数，表示测验题答案。 样例输入

4
1 2 3 4

样例输出

2

数据范围

，集合中所有的数字保证小于等于. ## 题目分析

数据范围不大，暴力查找。时间复杂度。注意，只要找到一个算式使之加起来等于就可以进行下一个了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
long long a[1001];
bool checka[10000001];//标记
int main()
{
    int n;
    cin>>n;
    long long max1=-1;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        max1=max(max1,a[i]);
    }
    for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)
    {
        ll s=a[i]+a[j];
        if(!checka[s]&&s<=max1)//存在c
        {
            checka[s]=true;
            for(int k=1;k<=n;k++)
            {
                if(a[k]==s)
                {
                    ans++;
                    break;
                }
            }
        }
    }
    cout<<ans<<endl;
    system("pause");
    return 0;
}

2.8 Monthly Expense

题目信息

题目描述：

给出天中每天的花费，需要将这些天分成组，每组包含连续的一或多天，若第组的花费为，求一种分组方法使得最小。

输入

输入数据第一行为两个正整数和，之后输入个正整数，分别表示第天的费用。输出包含一行，表示上面描述的。

输出

对于每组数据，输出一个数表示最小的花费。

样例输入

7 5
100
400
300
100
500
101
400

样例输出

500

数据范围

题目分析

这是一个相当经典的二分最值问题，但是非常的隐蔽，没有见过的话相当没有头绪。

二分算法的使用条件：

1. 答案在一个固定的区间里。
2. 答案的判断条件具有二段性。如果答案不在左区间的右端点，那么一定不在左区间，右区间同理。
3. 答案唯一性。

对于这个题目，逐一检验二分算法的条件。

1. 求的最小值，答案具有唯一性。
2. 组的分组最少分组，最大值为总价值之和；组的分组最多为组，的最小值为单日价值的最小值.所以，区间固定且答案必在该区间内。
3. 对于某一个可能的满足条件的,即每一组的总价值不大于，如果分的组数大于要求的组，证明该可能满足的小于目标答案，及其以下的值均不成立；如果分的组数小于等于，证明该可能满足的大于等于目标答案，以上的值均不满足条件，答案判断条件具有二段性。

故可以使用二分算法，最终结果即为满足的结果。

#include <bits/stdc++.h>
using namespace std;
int a[101];
int n, m;
bool check(int mid)//判断函数，返回false即在K0假想下分的组数m’大于规定组数m；反之为true。
{
    int count = 0, num = 1;
    for (int i = 1; i <= n; i++)
    {
        if (count <= mid)
            count += a[i];
        if (count > mid)//不能用else，加多了回退加组操作。
            count = a[i], num++;
    }
    if (num <= m)
        return true;
    else
        return false;
}
int ans = 0;
void searcher(int first, int last)
{
    if (first == last)//指针相撞二分结束，即最终结果
    {
        ans = first;
        return;
    }
    else
    {
        int mid = (first + last) / 2;
        if (check(mid))//返回为真，区间缩小到[a,K]，因为K可能成立，K以上不成立。
        {
            last = mid;
            searcher(first, last);
            return;
        }
        else//返回为假，区间缩小到[K+1,b],因为K及以下均不成立
        {
            first = mid + 1;
            searcher(first, last);
            return;
        }
    }
}
int main()
{

    cin >> n >> m;
    int first = -1, last = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        last += a[i];
        first = max(first, a[i]);
    }
    searcher(first, last);
    cout << ans << endl;
    system("pause");
    return 0;
}