C语言详解数据结构与算法中枚举和模拟及排序

#include <bits/stdc++.h>

using namespace std;

const int N=10010;

int a[N],bac[N];

int main()
{
    int n,res=0;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];

    for(int i=1;i<=n;i++)
       for(int j=i;j<=n;j++){
            memcpy(bac,a,sizeof a); // 这里要把数组的初始状态存在bac数组中，因为每次sort排序后，数组的顺序会发生改变。
            sort(a+i,a+j+1);

            bool flag=true;
            for(int k=i;k<j;k++){ 
                if(a[k+1] - a[k] != 1){
                    flag=false;
                    break;
                }
            }

            if(flag) res++;
            memcpy(a,bac,sizeof a); // 还原数组a的初始状态
        }
    cout << res << endl;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 10010, INF = 100000000;

int n;
int a[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    int res = 0;
    for (int i = 0; i < n; i ++ )   // 枚举区间左端点
    {
        int minv = INF, maxv = -INF;
        for (int j = i; j < n; j ++ )   // 枚举区间右端点
        {
            minv = min(minv, a[j]);
            maxv = max(maxv, a[j]);
            if (maxv - minv == j - i) res ++ ;
        }
    }

    cout << res << endl;

    return 0;
}

//暴力做法枚举（会超时）
#include <bits/stdc++.h>

using namespace std;


const int N=10000;

int n,a[N],b[N],c[N];
int cnt=0;
int main(){
    //输入
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    for(int i=0;i<n;i++) cin>>c[i];
    //运算
    for(int i=0;i<n;i++)
    	for(int j=0;j<n;j++)
    		for(int k=0;k<n;k++)
        		if(a[i]<b[j]&&b[j]<c[k])
	            cnt++;
    cout<<cnt<<endl;
    return 0;
}

//二分查找
#include <bits/stdc++.h>

using namespace std;

const int N=100000+6;

int n,a[N],b[N],c[N];
long long res=0;
int main(){
    cin>>n;//输入
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    for(int i=0;i<n;i++) cin>>c[i];
    //排序
    sort(a,a+n);sort(b,b+n);sort(c,c+n);
    //查找
    for(int i=0;i<n;i++)
    {
        int low_a=0,right_a=n-1;
        while(low_a<right_a)    //找比b[i]小的最后一个数
        {
            int mid=(low_a+right_a+1)>>1;//加1之后改为向上取整
            if(a[mid]<b[i])  low_a=mid;
            else  right_a=mid-1;
        }
        if(a[low_a]>=b[i]) low_a=-1;//所有数都大于等于b[i]的时候，low_a=-1,这样最后(low_a+1)*(n-low_b)的时候为0

        int low_b=0,right_b=n-1;
        while(low_b<right_b)   //找比b[i]大的第一个数
        {
            int mid =(low_b+right_b)>>1;
            if(c[mid]>b[i]) right_b=mid;
            else low_b=mid+1;
        }
        if(c[low_b]<=b[i]) low_b=n;//所有数都小于等于b[i]的时候，low_b=n,这样最后(low_a+1)*(n-low_b)的时候为0
        //if(low_a!=0&&low_b!=n-1)//最开始的时候用这种方法判断，后来发现不行
         //如果只有一个数字可以的时候，这种情况无法判断，
         // 例如：
         //  1 4 5
         //  5 5 9
         //  4 6 7（10）  当b[i]=9的时候，c[i]=7和10的时候无法判断
        res+=(long long)(low_a+1)*(n-low_b);

    }
    cout<<res<<endl;

    return 0;
}

//二分
for(int i = 1; i <= n; ++i) {
    int key = num[1][i];
    //A中二分查找第一个小于key的数的下标
    int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1;
    //C中二分查找第一个大于key的数的下标
    int pos2 = upper_bound(num[2]+1, num[2]+n+1, key)-num[2];
    if(pos1 >= 1 && pos2 <= n) {
        ans += (LL)pos1*(n-pos2+1);
    }
}

//双指针
int a = 1, c = 1;
for(int i = 1; i <= n; ++i) {
    int key = num[1][i];
    while(a<=n && num[0][a] < key) a++;
    while(c<=n && num[2][c] <= key) c++;

    ans += (LL)(a-1)*(n-c+1);
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e5+10;

int num[3][N];

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < 3; ++i) 
        for(int j = 1; j <= n; ++j) 
            scanf("%d", &num[i][j]);
    for(int i = 0; i < 3; ++i)
        sort(num[i]+1, num[i]+n+1);

    LL ans = 0;
    //枚举B，寻找A满足的个数以及C满足的个数相乘
    int a = 1, c = 1;
    for(int i = 1; i <= n; ++i) {
        int key = num[1][i];
        while(a<=n && num[0][a] < key) a++;
        while(c<=n && num[2][c] <= key) c++;

        ans += (LL)(a-1)*(n-c+1);

    }
    cout<<ans<<endl;
    return 0;
}

//前缀和
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1e5+10;
int A[N], B[N], C[N];
int cnta[N], cntc[N], sa[N], sc[N];

int main() {
    int n;
    scanf("%d", &n);
    //获取数i在A中有cntc[i]个，并对cnt求前缀和sa
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &A[i]);
        cnta[++A[i]]++;
    }
    sa[0] = cnta[0];
    for(int i = 1; i < N; ++i) sa[i] = sa[i-1]+cnta[i];
    //B只读取即可
    for(int i = 1; i <= n; ++i) scanf("%d", &B[i]), B[i]++;

    //获取数i在C中有cntc[i]个，并对cnt求前缀和sc
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &C[i]);
        cntc[++C[i]]++;
    }
    sc[0] = cntc[0];
    for(int i = 1; i < N; ++i) sc[i] = sc[i-1]+cntc[i]; 

    //遍历B求解
    LL ans = 0;
    for(int i = 1; i <= n; ++i) {
        int b = B[i];
        ans += (LL)sa[b-1] * (sc[N-1] - sc[b]);
    }
    cout<<ans<<endl;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int x = i;
        while (x)
        {
            int t = x % 10; // 取出x的个位
            x /= 10;    // 删掉x的个位
            if (t == 2 || t == 0 || t == 1 || t == 9)
            {
                res += i;
                break;
            }
        }
    }

    cout << res << endl;

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

int n;
int a[N];

int main()
{
    int cnt;
    cin >> cnt;
    string line;

    getline(cin, line); // 忽略掉第一行的回车
    while (cnt -- )
    {
        getline(cin, line);
        stringstream ssin(line);

        while (ssin >> a[n]) n ++ ;
    }

    sort(a, a + n);

    int res1, res2;
    for (int i = 1; i < n; i ++ )
        if (a[i] == a[i - 1]) res2 = a[i];  // 重号
        else if (a[i] >= a[i - 1] + 2) res1 = a[i] - 1; // 断号

    cout << res1 << ' ' << res2 << endl;

    return 0;
}

#include <iOStream>

using namespace std;

const int N = 100010;

int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);

    return 0;
}

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], tmp[N];

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    merge_sort(a, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);

    return 0;
}