第四讲 枚举模拟排序

枚举模拟排序

例题1：连号区间数

https://www.acwing.com/problem/content/1212/

小明这些天一直在思考这样一个奇怪而有趣的问题：

在 1∼N 的某个排列中有多少个连号区间呢？

这里所说的连号区间的定义是：

如果区间 [L,R][L,R] 里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R−L+1 的“连续”数列，则称这个区间连号区间。

当 N 很小的时候，小明可以很快地算出答案，但是当 N 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

输入格式

第一行是一个正整数 N，表示排列的规模。

第二行是 N 个不同的数字 Pi，表示这 N 个数字的某一排列。

输出格式

输出一个整数，表示不同连号区间的数目。

数据范围

1≤N≤10000
1≤Pi≤N

输入样例1：

  1. 4
  2. 3 2 4 1

输出样例1：

  1. 7

输入样例2：

  1. 5
  2. 3 4 2 5 1

输出样例2：

  1. 9

样例解释

第一个用例中，有 7 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4]
第二个用例中，有 9 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5]

C++代码：

  1. /*
  2. 方法1：枚举左端点和右端点，得到一个区间判断是否是连续区间。
  3.     判断是否是连续区间：sort在找每个数
  4. 方法2：枚举左端点l和右端点r，找到区间中最小的数minv和最大的数maxv,
  5.     如果maxv - minv == r - l，那么就是连续区间
  6. */
  8. #include <cstdio>
  9. #include <cstring>
  10. #include <iostream>
  11. #include <algorithm>
  12. using namespace std;
  14. const int N = 10010,INF = 10010;
  15. int p[N];
  17. int main() {
  18.     int n;
  19.     cin >> n;
  20.     for(int i = 0; i < n; i++) scanf("%d",&p[i]);
  22.     int res = 0;
  23.     for(int l = 0; l < n; l++){
  24.         int minv = INF,maxv = -INF;
  25.         for(int r = l; r < n; r++){
  26.             if(p[r] < minv) minv = p[r];
  27.             if(p[r] > maxv) maxv = p[r];
  29.             if(maxv - minv == r-l) res++;
  30.         }
  31.     }
  32.     cout << res << endl;
  33.     return 0;
  34. }

例题2：递增三元组

https://www.acwing.com/problem/content/1238/

给定三个整数数组

A=[A1,A2,…AN]
B=[B1,B2,…BN]
C=[C1,C2,…CN]

请你统计有多少个三元组 (i,j,k)满足：

  1. 1≤i,j,k≤N
  2. Ai<Bj<Ck

输入格式

第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,…AN。

第三行包含 N 个整数 B1,B2,…BN。

第四行包含 N 个整数 C1,C2,…CN。

输出格式

一个整数表示答案。

数据范围

1≤N≤10^5
0≤Ai,Bi,Ci≤10^5

输入样例：

  1. 3
  2. 1 1 1
  3. 2 2 2
  4. 3 3 3

输出样例：

  1. 27

c++代码：

  1. /*
  2. 遍历B，在A中找有几个数(n)小于Bj，在C中找有几个数(m)大于Bj
  3. n * m就是一组Bj的解数，再加起来 
  4. */
  6. #include <cstdio>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <algorithm>
  10. using namespace std;
  12. typedef long long LL;
  14. const int N = 1e5 + 10;
  15. int a[N],b[N],c[N];
  16. int as[N];    //表示as[i]表示在a[]中有多少个数小于b[i] 
  17. int cs[N];    //表示cs[i]表示在c[]中有多少个数大于b[i]
  18. int cnt[N],s[N]; 
  20. int main() {
  21.     int n;
  22.     cin >> n;
  23.     for(int i = 0; i < n; i++) scanf("%d",&a[i]),a[i]++;
  24.     for(int i = 0; i < n; i++) scanf("%d",&b[i]),b[i]++;
  25.     for(int i = 0; i < n; i++) scanf("%d",&c[i]),c[i]++;
  27.     //遍历a[]，找到每个数出现的次数存入cnt[]中 
  28.     for(int i = 0; i < n; i++) cnt[a[i]]++;
  29.     //初始化前缀和s,前缀和下标最好从1开始 
  30.     for(int i = 1; i < N; i++) s[i] = s[i-1] + cnt[i];
  31.     //s[i]表示从a中从1一直加到i的值，即a中<=i的数有多少个 
  32.     //写入as 
  33.     for(int i = 0; i < n; i++) as[i] = s[b[i] - 1];
  35.     //CS同理
  36.     memset(cnt, 0, sizeof cnt);
  37.     memset(s, 0, sizeof s);
  38.     for(int i = 0; i < n; i++) cnt[c[i]] ++;
  39.     for(int i = 1; i < N; i++) s[i] = s[i-1] + cnt[i];
  40.     for(int i = 0; i < n; i++) cs[i] = s[N-1] - s[b[i]];
  42.     //遍历b
  43.     LL res = 0;
  44.     for(int i = 0; i < n ; i++){
  45.         res += (LL)as[i] * cs[i];
  46.     }
  47.     cout << res << endl;
  48.     return 0;
  49. }

例题3：特别数的和

https://www.acwing.com/problem/content/1247/

小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。

请问，在 1 到 n 中，所有这样的数的和是多少？

输入格式

共一行，包含一个整数 n。

输出格式

共一行，包含一个整数，表示满足条件的数的和。

数据范围

1≤n≤10000

输入样例：

  1. 40

输出样例：

  1. 574

C++代码：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  7. int main() {
  8.     int n;
  9.     cin >> n;
  11.     int res = 0;
  12.     for(int i = 1; i <= n; i++){
  13.         int x = i;
  14.         while(x){
  15.             int t = x%10;
  16.             x/=10;
  17.             if(t==2 || t==0 || t==1 || t==9){
  18.                 res += i;
  19.                 break;
  20.             }
  21.         }
  22.     }
  23.     cout << res << endl;
  24.     return 0;
  25. }

例题4：错误票据

https://www.acwing.com/problem/content/1206/

某涉密单位下发了某种票据，并要在年终全部收回。

每张票据有唯一的ID号。

全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。

因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。

你的任务是通过编程，找出断号的ID和重号的ID。

假设断号不可能发生在最大和最小号。

输入格式

第一行包含整数 N，表示后面共有 N 行数据。

接下来 N 行，每行包含空格分开的若干个（不大于100个）正整数（不大于100000），每个整数代表一个ID号。

输出格式

要求程序输出1行，含两个整数 m,n，用空格分隔。

其中，m表示断号ID，n表示重号ID。

数据范围

1≤N≤100

输入样例：

  1. 2
  2. 5  6  8  11  9
  3. 10  12  9

输出样例：

  1. 7 9

C++代码：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <sstream>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  8. const int N = 110 * 110;
  9. int a[N];
  11. int main() {
  12.     int cnt;
  13.     cin >> cnt;
  14.     string line;
  16.     getline(cin,line);    //忽略掉第一行的回车
  18.     int n = 0;
  19.     while(cnt--){
  20.         getline(cin,line);
  21.         stringstream ss(line);
  22.         while(ss >> a[n]) n++;
  23.     }
  24.     sort(a,a+n);
  26.     int rm,rn;    //断号id和重号id 
  27.     for(int i = 1; i < n; i++){
  28.         if(a[i] == a[i-1]) rn = a[i];    //重号 
  29.         else if(a[i] == a[i-1] + 2) rm = a[i]-1;    //断号 
  30.     }
  31.     cout << rm << " " << rn << endl;
  33.     return 0;
  34. }

例题5：回文七日

https://www.acwing.com/problem/content/468/

在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。

牛牛习惯用 8 位数字表示一个日期，其中，前 4 位代表年份，接下来 2 位代表月份，最后 2 位代表日期。

显然：一个日期只有一种表示方法，而两个不同的日期的表示方法不会相同。

牛牛认为，一个日期是回文的，当且仅当表示这个日期的8位数字是回文的。

现在，牛牛想知道：在他指定的两个日期之间（包含这两个日期本身），有多少个真实存在的日期是回文的。

一个 8 位数字是回文的，当且仅当对于所有的 i(1≤i≤8) 从左向右数的第i个数字和第 9−i 个数字（即从右向左数的第 i 个数字）是相同的。

例如：

•对于2016年11月19日，用 8 位数字 20161119 表示，它不是回文的。

•对于2010年1月2日，用 8 位数字 20100102 表示，它是回文的。

•对于2010年10月2日，用 8 位数字 20101002 表示，它不是回文的。

输入格式

输入包括两行，每行包括一个8位数字。

第一行表示牛牛指定的起始日期date1，第二行表示牛牛指定的终止日期date2。保证date1和date2都是真实存在的日期，且年份部分一定为4位数字，且首位数字不为0。

保证date1一定不晚于date2。

输出格式

输出共一行，包含一个整数，表示在date1和date2之间，有多少个日期是回文的。

输入样例：

  1. 20110101
  2. 20111231

输出样例：

  1. 1

C++代码：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  7. const int table[13] = {
  8.     0,31,28,31,30,31,30,31,31,30,31,30,31,
  9. };
  11. bool check(int num) {
  12.     int year = num / 10000;
  13.     int mon = num % 10000 / 100;
  14.     int day = num % 100;
  15.     if(mon < 1 || mon > 12) return false;
  17.     int leap = 0;
  18.     if(mon == 2){
  19.         if(year%4==0 && year%100!=0 || year%400==0) leap = 1;
  20.     }
  21.     if(day < 1 || day > table[mon]+leap) return false;
  23.     return true;
  24. }
  26. int main() {
  27.     int date1,date2;    //开始日期、结束日期 
  28.     cin >> date1 >> date2;
  30.     //遍历所有回文
  31.     int res = 0;
  32.     for(int i = 1000; i <= 9999; i++){
  33.         int num = i;
  34.         int x = i;
  35.         //将num拼凑成回文8位
  36.         while(x){
  37.             int t = x%10;
  38.             num = num * 10 + t;
  39.             x/=10;
  40.         }
  42.         if(num < date1 || num > date2) continue;
  43.         if(check(num)) res ++;
  44.     }
  45.     cout << res << endl;
  46.     return 0;
  47. }

例题6：归并排序

https://www.acwing.com/problem/content/789/

给定你一个长度为n的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在1~10^9范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

输入样例：

  1. 5
  2. 3 1 2 4 5

输出样例：

  1. 1 2 3 4 5

C++代码：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  7. const int N = 100010;
  8. int n;
  9. int a[N],t[N];
  11. void merge_sort(int l, int r) {
  12.     if(l >= r) return;
  14.     int mid = l + r >> 1;
  16.     merge_sort(l,mid), merge_sort(mid+1,r);
  18.     int i = l, j = mid + 1, k = 0;    //左半边起点，右半边起点
  19.     while(i <= mid && j <= r) {
  20.         if(a[i] < a[j]) t[k++] = a[i++];
  21.         else t[k++] = a[j++];
  22.     }
  23.     while(i <= mid) t[k++] = a[i++];
  24.     while(j <= r) t[k++] = a[j++];
  26.     for(i = l, j = 0; i <= r; i++, j++) a[i] = t[j];
  27. }
  29. int main() {
  30.     cin >> n;
  32.     for(int i = 0; i < n; i++) scanf("%d",&a[i]);
  33.     merge_sort(0,n-1);
  34.     for(int i = 0; i < n; i++) printf("%d ",a[i]);
  36.     return 0;
  37. }

作业1：移动距离

https://www.acwing.com/problem/content/1221/

X星球居民小区的楼房全是一样的，并且按矩阵样式排列。

其楼房的编号为 1,2,3…

当排满一行时，从下一行相邻的楼往反方向排号。

比如：当小区排号宽度为 6 时，开始情形如下：

  1. 1  2  3  4  5  6
  2. 12 11 10 9  8  7
  3. 13 14 15 .....

我们的问题是：已知了两个楼号 m 和 n，需要求出它们之间的最短移动距离（不能斜线方向移动）。

输入格式

输入共一行，包含三个整数 w,m,n，w 为排号宽度，m,n 为待计算的楼号。

输出格式

输出一个整数，表示 m,n 两楼间最短移动距离。

数据范围

1≤w,m,n≤10000

输入样例：

  1. 6 8 2

输出样例：

  1. 4

方法1：直接模拟

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  8. const int N = 10010;
  10. int main() {
  11.     int w,m,n;
  12.     cin >> w >> m >> n;
  13.     int cnt = (int)(ceil((double)max(m,n) / w));
  15.     bool flag = false;
  16.     int i = 0,j = 0,nb = 1;
  17.     int ai,aj,bi,bj; 
  18.     while(i < cnt){
  19.         if(nb == n) ai = i, aj = j;
  20.         if(nb == m) bi = i, bj = j;
  22.         if(!flag){
  23.             j++;
  24.             if(j==w){
  25.                 j--;
  26.                 flag = !flag;
  27.                 i++;
  28.             }
  29.         }else{
  30.             j--;
  31.             if(j==-1){
  32.                 j++;
  33.                 flag = !flag;
  34.                 i++;
  35.             }
  36.         }
  38.         nb++;
  39.     }
  40.     int res = abs(bj - aj) + abs(bi - ai);
  41.     cout << res << endl;
  42.     return 0;
  43. }

方法2：找映射关系

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  8. int main() {
  9.     int w,m,n;
  10.     cin >> w >> m >> n;
  11.     m--,n--;
  12.     int x1 = m/w, x2 = n/w;
  13.     int y1 = m%w, y2 = n%w;
  14.     if(x1 % 2 == 1) y1 = (w-1-y1);
  15.     if(x2 % 2 == 1) y2 = (w-1-y2);
  16.     cout << abs(x2-x1) + abs(y2-y1) << endl;
  17.     return 0;
  18. }

作业2：日期问题

https://www.acwing.com/problem/content/1231/

小明正在整理一批历史文献。这些历史文献中出现了很多日期。

小明知道这些日期都在1960年1月1日至2059年12月31日。

令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。

更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。

比如02/03/04，可能是2002年03月04日、2004年02月03日或2004年03月02日。

给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？

输入格式

一个日期，格式是”AA/BB/CC”。

即每个’/’隔开的部分由两个 0-9 之间的数字（不一定相同）组成。

输出格式

输出若干个不相同的日期，每个日期一行，格式是”yyyy-MM-dd”。

多个日期按从早到晚排列。

数据范围

0≤A,B,C≤9

输入样例：

  1. 02/03/04

输出样例：

  1. 2002-03-04
  2. 2004-02-03
  3. 2004-03-02

mycode:

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <set>
  6. using namespace std;
  8. const int table[13] = {
  9.     0,31,28,31,30,31,30,31,31,30,31,30,31,
  10. };
  12. set<int> st;
  14. bool check(int year,int mon,int day){
  15.     if(year < 1960 || year > 2059) return false;//特判 
  17.     if(mon < 1 || mon > 12) return false;
  18.     int leap = 0;
  19.     if(mon == 2){
  20.         if(year%4==0&&year%100!=0 || year%400==0) leap++;
  21.     }
  22.     if(day < 1 || day > table[mon] + leap) return false;
  24.     return true;
  25. }
  27. int main() {
  28.     int n1,n2,n3;
  29.     scanf("%d/%d/%d",&n1,&n2,&n3);
  30.     int cnt = 0;
  31.     //年月日
  32.     int year = n1, mon = n2, day = n3;
  33.     if(check(1900+year,mon,day)) st.insert((1900+year)*10000 + mon*100 + day);
  34.     if(check(2000+year,mon,day)) st.insert((2000+year)*10000 + mon*100 + day);
  35.     //月日年
  36.     mon = n1, day = n2, year = n3;
  37.     if(check(1900+year,mon,day)) st.insert((1900+year)*10000 + mon*100 + day);
  38.     if(check(2000+year,mon,day)) st.insert((2000+year)*10000 + mon*100 + day);
  39.     //日月年
  40.     day = n1, mon = n2, year = n3;
  41.     if(check(1900+year,mon,day)) st.insert((1900+year)*10000 + mon*100 + day);
  42.     if(check(2000+year,mon,day)) st.insert((2000+year)*10000 + mon*100 + day);
  44.     for(set<int>::iterator it = st.begin(); it != st.end(); it++) {
  45.         int num = *it;
  46.         printf("%d-%02d-%02d\n",num/10000,num/100%100,num%100);
  47.     }
  49.     return 0;
  50. }

y总code：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  6. using namespace std;
  8. int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  10. bool check_valid(int year, int month, int day)
  11. {
  12.     if (month == 0 || month > 12) return false;
  13.     if (day == 0) return false;
  14.     if (month != 2)
  15.     {
  16.         if (day > days[month]) return false;
  17.     }
  18.     else
  19.     {
  20.         int leap = year % 100 && year % 4 == 0 || year % 400 == 0;
  21.         if (day > 28 + leap) return false;
  22.     }
  24.     return true;
  25. }
  27. int main()
  28. {
  29.     int a, b, c;
  30.     scanf("%d/%d/%d", &a, &b, &c);
  32.     for (int date = 19600101; date <= 20591231; date ++ )
  33.     {
  34.         int year = date / 10000, month = date % 10000 / 100, day = date % 100;
  35.         if (check_valid(year, month, day))
  36.         {
  37.             if (year % 100 == a && month == b && day == c ||        // 年/月/日
  38.                 month == a && day == b && year % 100 == c ||        // 月/日/年
  39.                 day == a && month == b &&year % 100 == c)           // 日/月/年
  40.                 printf("%d-%02d-%02d\n", year, month, day);
  41.         }
  42.     }
  44.     return 0;
  45. }

作业3：航班时间

https://www.acwing.com/problem/content/1233/

小 h 前往美国参加了蓝桥杯国际赛。

小 h 的女朋友发现小 h 上午十点出发，上午十二点到达美国，于是感叹到“现在飞机飞得真快，两小时就能到美国了”。

小 h 对超音速飞行感到十分恐惧。

仔细观察后发现飞机的起降时间都是当地时间。

由于北京和美国东部有 12小时时差，故飞机总共需要 14 小时的飞行时间。

不久后小 h 的女朋友去中东交换。

小 h 并不知道中东与北京的时差。

但是小 h 得到了女朋友来回航班的起降时间。

小 h 想知道女朋友的航班飞行时间是多少。

对于一个可能跨时区的航班，给定来回程的起降时间。

假设飞机来回飞行时间相同，求飞机的飞行时间。

输入格式

一个输入包含多组数据。

输入第一行为一个正整数 T，表示输入数据组数。

每组数据包含两行，第一行为去程的起降时间，第二行为回程的起降时间。

起降时间的格式如下:

  1. h1:m1:s1 h2:m2:s2
  2. h1:m1:s1 h3:m3:s3 (+1)
  3. h1:m1:s1 h4:m4:s4 (+2)

第一种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间当日h2时m2分s2秒降落。

第二种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间次日h2时m2分s2秒降落。

第三种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间第三日h2时m2分s2秒降落。

输出格式

对于每一组数据输出一行一个时间hh:mm:ss，表示飞行时间为hh小时mm分ss秒。

注意，当时间为一位数时，要补齐前导零，如三小时四分五秒应写为03:04:05。

数据范围

保证输入时间合法（0≤h≤23,0≤m,s≤59），飞行时间不超过24小时。

输入样例：

  1. 3
  2. 17:48:19 21:57:24
  3. 11:05:18 15:14:23
  4. 17:21:07 00:31:46 (+1)
  5. 23:02:41 16:13:20 (+1)
  6. 10:19:19 20:41:24
  7. 22:19:04 16:41:09 (+1)

输出样例：

  1. 04:09:05
  2. 12:10:39
  3. 14:22:05

code:

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  7. int get_seconds(int h, int m, int s){
  8.     return h * 3600 + m * 60 + s;
  9. }
  11. int get_time(){
  12.     string line;
  13.     getline(cin, line);
  15.     if (line.back() != ')') line += " (+0)";
  17.     int h1, m1, s1, h2, m2, s2, d;
  18.     sscanf(line.c_str(), "%d:%d:%d %d:%d:%d (+%d)", &h1, &m1, &s1, &h2, &m2, &s2, &d);
  20.     return get_seconds(h2, m2, s2) - get_seconds(h1, m1, s1) + d * 24 * 3600;
  21. }
  23. int main(){
  24.     int n;
  25.     scanf("%d", &n);
  26.     string line;
  27.     getline(cin, line);    //获得一个差值 
  28.     while (n -- ){
  29.         int time = (get_time() + get_time()) / 2;
  30.         int hour = time / 3600, minute = time % 3600 / 60, second = time % 60;
  31.         printf("%02d:%02d:%02d\n", hour, minute, second);
  32.     }
  34.     return 0;
  35. }

作业4： 外卖店的优先级

https://www.acwing.com/problem/content/1243/

“饱了么”外卖系统中维护着 N 家外卖店，编号 1∼N。

每家外卖店都有一个优先级，初始时 (0 时刻) 优先级都为 0。

每经过1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。

如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果优先级小于等于 3，则会被清除出优先缓存。

给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优先缓存中。

输入格式

第一行包含 3 个整数 N,M,T。

以下 M 行每行包含两个整数 ts 和 id，表示 ts 时刻编号 id的外卖店收到一个订单。

输出格式

输出一个整数代表答案。

数据范围

1≤N,M,T≤10^5
1≤ts≤T
1≤id≤N

输入样例：

  1. 2 6 6
  2. 1 1
  3. 5 2
  4. 3 1
  5. 6 2
  6. 2 1
  7. 6 2

输出样例：

1

样例解释

6 时刻时，1 号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6，加入优先缓存。

所以是有 1 家店 (2 号) 在优先缓存中。

code:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second
using namespace std;

typedef pair<int,int> PII;

const int N = 1e5 + 10;
PII order[N];    //订单<时刻，店铺id> 
int last[N];    //记录i店铺上一次有订单的时刻
int score[N];    //记录i店铺的优先级 
bool st[N];        //记录i店铺是否加入了优先缓存 

int main() {
    int n,m,T;    //n家店，m条订单，总时刻T
    cin >> n >> m >> T;
    for(int i = 0; i < m; i++) scanf("%d%d",&order[i].x,&order[i].y);
    sort(order,order+m);//以时刻为主升序 
    //枚举每个订单 
    for(int i = 0; i < m;) {
        //处理相同的一批订单（也就是同一时刻，同一个店铺的n个订单） 
        int j = i;
        while(j < m && order[j] == order[i]) j++;
        //j定位到了下一批订单的起始位置 
        //得到该批订单的时刻 和 店铺id，以及订单数量 
        int t = order[i].x, id = order[i].y, cnt = j - i;
        i = j;    //i定位到下一批订单的起始位置 

        score[id] -= t - last[id] - 1;
        //减去没有订单时候要下降的分（这个分数是中间间隔的没有订单的时间）。
        if(score[id] < 0) score[id] = 0;
        if(score[id] <= 3) st[id] = false;
        //以上是处理该批订单之前的真空期 

        score[id] += cnt*2;    // 加上2分一单的优先级 
        if(score[id] > 5) st[id] = true;

        //更新该店铺上一次有订单的时刻
        last[id] = t; 
    }
    //每个店铺最后的真空期给减掉
    for(int i = 1; i <= n; i++) {
        if(last[i] != T) {    //最后一个时刻没有订单 
            score[i] -= T - last[i];
            if(score[i] < 0) score[i] = 0;
            if(score[i] <= 3) st[i] = false;
        }
    }
    //遍历店铺的优先情况 
    int res = 0;
    for(int i = 1; i <= n; i++) {
        if(st[i]) res ++;
    }
    cout << res << endl;
    return 0;    
}

作业5：逆序对的数量

https://www.acwing.com/problem/content/790/

给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。

输入格式

第一行包含整数n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

1≤n≤100000

输入样例：

6
2 3 4 5 6 1

输出样例：

5

code:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;
int a[N],t[N];
long long res = 0;

void merge_sort(int l, int r) {
    if(l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l,mid), merge_sort(mid+1,r);

    //归并
    int k = 0, i = l, j = mid + 1; 
    while(i <= mid && j <= r) {
        if(a[i] <= a[j]) t[k++] = a[i++];
        else {
            t[k++] = a[j++];
            res += (mid-i+1);
        }
    }

    //扫尾
    while(i <= mid) t[k++] = a[i++];
    while(j <= r) t[k++] = a[j++];

    //复制回去
    for(i = l, j = 0; i <= r; i++, j++) a[i] = t[j];
}

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d",&a[i]);
    merge_sort(0,n-1);
    cout << res << endl;
    return 0;
}