//method 1
class Solution {
public:

    int findPairs(vector<int>& nums, int k) {
         int res = 0;
         sort(nums.begin(),nums.end());
         int n = nums.size();

         for(int i = 0, j = 0; i < n;i++)
         {
             while(i > 0 && i < n - 1 && nums[i + 1] == nums[i]) i++;

             while(j < i && nums[i] - nums[j] > k) j++;
             if(j < i && nums[i] - nums[j] == k) res++;
         }
        return res;
    }  
};\
//method 2 

class Solution {
public:
      unordered_map<int,int> less;
      unordered_map<int,int> greater;
    int findPairs(vector<int>& nums, int k) {
             int n = nums.size();
             int res = 0;
          for(int i = 0; i < n;i++)
          {
              if(less.count(nums[i] - k))
              {
                  if(!greater.count(nums[i])) greater[nums[i]]++;
              }
                if(less.count(nums[i] + k))
              {
                  if(!greater.count(nums[i] + k)) greater[nums[i]+k]++;
              }
              if(!less.count(nums[i])) less[nums[i]]++;



          }

          res = greater.size();

          return res;
    } 
};

#include<bits/stdc++.h>

using namespace std;

const int N = 110;
int n,k;
int g[N][N];
bool st[N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
    int a = 0, b = 0, m = 0;
    for(int i = 0; i < n * k; i++ )
    {
         g[a][b] = i + 1;
          st[a][b] = true;
         int ta = a, tb = b;
         a = a + dx[m], b = b + dy[m];
         if(a < 0 || a > n - 1 || b < 0 || b >  k - 1 || st[a][b])
         {

              m = (m + 1) % 4;
              a = ta + dx[m], b = tb + dy[m];
         }


    }

    for(int i = 0; i < n;i++)
    {

              for(int j = 0; j < k;j++)
          {

             cout << g[i][j] << " " ;
          }  


          cout <<  endl;
    }


    return 0;
}

排序算法的稳定性

九大排序

计数排序 基数排序 桶排序
选择排序 插入排序 冒泡排序
堆排序 归并排序 快速排序

什么是排序的稳定性
如果元素大小相同
排序后的相对位置不变

不稳定
堆排序 快速排序 选择排序 不是稳定的
稳定
基数排序 冒泡排序 插入排序 归并排序 计数排序 桶排序

选择排序
在每次将最小的元素拿到最前面和未排序的序列的第一个元素进行交换的时候发生了对原序列的破坏 失去了稳定性

快速排序
Swap的时候有可能让两个本来相等的元素交换位置 破坏了原序列的稳定性

堆排序
比如：3 27 36 27，
如果堆顶3先输出，则，第三层的27（最后一个27）跑到堆顶，然后堆稳定，继续输出堆顶，是刚才那个27，这样说明后面的27先于第二个位置的27输出，不稳定。

基数排序 计数排序 桶排序
基数 进入每个桶的顺序和一开始相对位置相同
计数 下标映射偏移和相对位置相同
桶 和基数同理

冒泡排序 基于比较换到一侧 相等的话不会交换位置 保证相对的有序
插入排序 因为如果两个元素相等不会发生交换 先插入的放在前面 保证相对位置不变
归并排序 相等则不发生交换 保证相对位置不变

#include<bits/stdc++.h>

using namespace std;
int n;
vector<int> chosen;
void calc(int x)
{

    if(x == n + 1)
    {
        for(int i = 0; i < chosen.size();i++) cout << chosen[i] << ' ';
        cout << endl;
        return;
    }
    calc(x+1); // not choose

    chosen.push_back(x);
    calc(x+1);
    chosen.pop_back();
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    calc(1);

    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 1000010;
int q[N],a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin >> n >> k; 
    for(int i = 0; i < n; i++) cin >> a[i];
    int hh = 0, tt = -1;
    for(int i = 0; i < n;i++)
    {
        if(hh <= tt && q[hh] < i - k + 1) hh++;
        while(hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++ tt] = i;
        if(i >= k - 1) cout << a[q[hh]] << ' ';

    }
    cout << endl;
    hh = 0, tt = -1;
    for(int i = 0; i < n;i++)
    {
        if(hh <= tt && q[hh] < i - k + 1) hh++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++ tt] = i;
        if(i >= k - 1) cout << a[q[hh]] << ' ';

    }

    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 1000010;
int q[N],a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin >> n >> k; 
    for(int i = 0; i < n; i++) cin >> a[i];
    int hh = 0, tt = -1;
    for(int i = 0; i < n;i++)
    {
        if(hh <= tt && q[hh] < i - k + 1) hh++;
        while(hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++ tt] = i;
        if(i >= k - 1) cout << a[q[hh]] << ' ';

    }
    cout << endl;
    hh = 0, tt = -1;
    for(int i = 0; i < n;i++)
    {
        if(hh <= tt && q[hh] < i - k + 1) hh++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++ tt] = i;
        if(i >= k - 1) cout << a[q[hh]] << ' ';

    }

    return 0;
}

#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
int stk[N],tt;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= n;i++) 
    {
        int x;
        cin >> x;
        while(tt && stk[tt] >= x) tt--;
        if(tt) cout << stk[tt] << ' ';
        else cout << "-1" << ' ';
        stk[++tt] = x;
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
long long a[N],b[N],f[N],avr;

long long calc(long long nums[],int t)
{


    for(int i = 1; i <= t;i++)
    {
        nums[i] -= nums[0] / t;
        nums[i] += nums[i-1];
    }
    sort(nums+1,nums+t+1);
    long long ans = 0;
    for(int i = 1; i <= t;i++)
    {
        ans += abs(nums[i] - nums[t+1>>1]);
    }
    return ans;
}



int main()
{
    ios::sync_with_stdio(false);

    long long n,m,t;
    cin >> n >> m >> t;
    while(t--)
    {
        int x,y;
        cin >> x >> y;
        a[x]++; b[y]++;

    }
    long long res = 0;

    for(int i = 1; i <= n;i++) a[0] += a[i];
    for(int i = 1; i <= n;i++) b[0] += b[i];
     if(a[0]%n==0&&b[0]%m==0)
        printf("both %lld\n",calc(a,n)+calc(b,m));
    else if(a[0]%n==0)
        printf("row %lld\n",calc(a,n));
    else if(b[0]%m==0)
        printf("column %lld\n",calc(b,m));
    else puts("impossible");

    return 0;
}

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n,a[1000001],c[1000001],ave;ll sum;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    ave=sum/n;

    for(int i=2;i<=n;i++)
       c[i]=c[i-1]+a[i]-ave;
    sort(c+1,c+n+1);



    ll ans=0;
    int mid=c[(n>>1)+1];
    for(int i=1;i<=n;i++)
       ans+=abs(c[i]-mid);
    printf("%lld",ans); 
    return 0;
}