数据结构的几个算法实例

a - buggy sorting

题意：这个题意就是给你一个错误的排序方式，要求你在它的这个排序方式下判断是否存在正确的运行结果。若存在正确的结果，则输出-1，否则输出一个例子说明是错误的。题目的输入是元素的个数n。

题解：这一题比较有意思，很容易判断出只有当n=1 or n=2时运行结果是正确的，其余的情况都是错误的。这样我们就构造出一个序列出来就可以了。

代码：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n<=2){
        cout<<-1;
    }else{
        for(int i=n;i>=1;i--){
            cout<<i;
            if(i!=1){
                cout<<" "; 
            }
        }
    }
    return 0;
} 

b - increase and decrease

题意：这一题的大概意思是给你一个长度为n的int序列。你可以选择其中任意两个数对其分别进行+1和-1操作，问在进行若干次后，最多可存在多少个相同的数。

题解：对同一个数组里面的两个元素进行+1和-1操作，很容易想到的一点是它的元素和总是一定的，这是一个突破点。这里我们判断元素的和是否能被n整除，如果能，则最多的个数就是n(说明一定存在某种方式将所有的元素变为一样的)，如果不能，就肯定存在一个余数，这时，我们就可以舍去这个元素，对其他的元素进行操作。则此时的元素个数就是n-1。

代码：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int main(){
    int n;
    cin>>n;
    int num[100005]={0};
    int sum=0;
    for(int i=0;i<n;i++){
        cin>>num[i];
        sum=sum+num[i];
    }
    if(sum%n==0){
        cout<<n<<endl;
    }else{
        cout<<n-1<<endl;
    }
    return 0;
} 

e - dividing orange

题意：这一题的大概意思是k个人平均分n*k个橘子，特别的是每个人都有它们各自必须必须需要的一个橘子，其他的没有要求。

题解：这一题也是比较简单的(悔不当初)，

代码：这里我们只需要用一个vis数组记录一下哪一个橘子被分了就可以，然后依次输出应有数量的橘子即可(同时特别关注该人特别需要橘子的编号这个需要特别判断一下)。

代码：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int main(){
    ll n,k;
    cin>>n>>k;
    int num[1000]={0};
    int vis[1000]={0}; 
    int t;
    for(int i=0;i<k;i++){ 
        cin>>vis[i];
        num[vis[i]]=1;
    }
    int len=0;
    for(int i=0;i<k;i++){
        len=0;
        cout<<vis[i]<<" ";
        len++;
        for(int j=1;j<=n*k;j++){
            if(len<n&&num[j]==0){
                cout<<j;
                num[j]=1;
                len++;
                if(len<=n-1){
                    cout<<" ";
                }
            }
        } 
        cout<<endl;
    } 
    return 0;
} 

f - undoubtedly lucky numbers

题意：这一题的大概意思它定义了一种特别的数，其中这个数字包含的单个数字的种类的数量不超过2种，现在给你n需要你求出在[1,n]之中存在多少个这样的数字。

题解：比赛想了半天就是没看出这是一个dfs，这里我们可以这样想，我们遍历[0,9]中全部的2种数字的组合，然后将它们去排列组合，小于n就放入set(可以去重)中，最后输出就可以了。

知识点：dfs 排列组合

代码：

#include<iostream>
#include<set>
#include<algorithm>
#define ll long long
using namespace std;
set<ll> st;
ll n;
void dfs(int a,int b,ll num){
    st.insert(num);
    ll ta=num*10+a;
    ll tb=num*10+b;
    if(ta&&ta<=n){
        dfs(a,b,ta);
    }
    if(tb&&tb<=n){
        dfs(a,b,tb);
    }
}
int main(){
    cin>>n;
    for(int i=0;i<=9;i++){
        for(int j=0;j<=9;j++){
            dfs(i,j,0);/*每个数字都是从0开始的*/
        }
    }
    cout<<st.size()-1;
    return 0;
}