Chapter4 枚举，模拟与排序
+++
-
枚举
1.连号区间数 1210
首先想到的就是暴力枚举，但是复杂度过高会超时。
接下来就想优化，由于本题输入的是不重复的连续的序列，因此找到连号区间的性质
即(a~b)的最大值减去最小值等于b - a，降低暴搜检查合法序列的复杂度
//复杂度O(n²)
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10010;
int a[maxn];
int n, res;
int main()
{
cin >> n;
for(int i = 0; i < n; i++ ) scanf("%d", a + i);
for(int i = 0; i < n; i++ )//枚举区间左端点
{
int Max = -1e9;
int Min = 1e9;
for(int j = i; j < n; j++ )//枚举区间右端点
{
Max = max(Max, a[j]);
Min = min(Min, a[j]);
if(Max - Min == j - i) {res++;continue;}
}
}
cout << res << endl;
return 0;
}
2.递增三元组 1236
首先观察数据范围，可以知道这题暴力做法必定超时，因此就想基于暴力做法的优化做法。
由数据范围可以知道我们最多只可以枚举一个数组元素，因此枚举处于中间位置的数组b，因为当b[]元素确定是，a与c的对应元素范围就会缩小。
针对每一个b[i]，我们可以知道只需要找到a[]中比b[i]小的元素个数和c[]中比b[i]大的元素个数，两个数相乘就是b[i]对结果的贡献值，最后累加所有贡献值就是答案。
因为结果范围过大，有可能会爆int，因此用long long 来声明结果res
//前缀和AC CODE
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;//防止结果爆int
const int maxn = 1e5 + 10;
int a[maxn], b[maxn], c[maxn];
int cnt[maxn], s[maxn];//s是cnt的前缀和数组，cnt是统计a[],c[]中每个数字出现的个数
int as[maxn], cs[maxn];//比b[]中某个元素大或者小的数字个数
int main()
{
int n;
cin >> n;
//输入
for(int i = 0; i < n; i++ ) scanf("%d", a + i), a[i]++;//防止计算前缀和数组是数组越界，下同
for(int i = 0; i < n; i++ ) scanf("%d", b + i), b[i]++;
for(int i = 0; i < n; i++ ) scanf("%d", c + i), c[i]++;
//计算as
for(int i = 0; i < n; i++ ) cnt[a[i]]++;
for(int i = 1; i < maxn; i++ ) s[i] = s[i - 1] + cnt[i];
for(int i = 0; i < n; i++ ) as[i] = s[b[i] - 1];//统计比b[]小的数字个数
memset(cnt, 0, sizeof cnt);
memset(s, 0, sizeof s);
for(int i = 0; i < n; i++ ) cnt[c[i]]++;
for(int i = 1; i < maxn; i++ ) s[i] = s[i - 1] + cnt[i];
for(int i = 0; i < n; i++ ) cs[i] = s[maxn - 1] - s[b[i]];//统计比b[]大的数字个数
LL res = 0;
for(int i = 0; i < n; i++ ) res += (LL)as[i] * cs[i];
cout << res << endl;
return 0;
}
//错误代码，还没找到问题
//样例是对的
//待解决
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], b[N], c[N];
int n;
LL acnt(int u)//二分计算a[]中小于b[i]的元素个数
{
int L = 0, R = n;
while(L < R)
{
int mid = (L + R) >> 1;
if(a[mid] >= u) R = mid;
else L = mid + 1;
}
return R;
}
LL ccnt(int u)//二分计算c[]中大于b[i]的元素个数
{
int L = 0, R = n;
while(L < R)
{
int mid = (L + R + 1) >> 1;
if(c[mid] <= u) L = mid;
else R = mid - 1;
}
return n - R;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++ ) scanf("%d", a + i);
for(int i = 0; i < n; i++ ) scanf("%d", b + i);
for(int i = 0; i < n; i++ ) scanf("%d", c + i);
//排序，为二分做准备
sort(a, a + n);
sort(c, c + n);
LL res = 0;
for(int i = 0; i < n; i++ )
res += acnt(b[i]) * ccnt(b[i]);
cout << res << endl;
return 0;
}
//STL二分函数AC CODE
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], b[N], c[N];
int n;
int main()
{
cin >> n;
for(int i = 0; i < n; i++ ) scanf("%d", a + i);
for(int i = 0; i < n; i++ ) scanf("%d", b + i);
for(int i = 0; i < n; i++ ) scanf("%d", c + i);
//从小到大排序，为二分做准备
sort(a, a + n);
sort(c, c + n);
LL res = 0;
for(int i = 0; i < n; i++ )
{
LL x = lower_bound(a, a + n, b[i]) - a;
LL y = n - (upper_bound(c, c + n, b[i]) - c);
res += x * y;
}
cout << res << endl;
return 0;
}
-
模拟
1.特别数的和 1245
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int n, sum = 0;
cin >> n;
for(int i = 1; i <= n; i++ )
{
int x = i;
while(x)
{
int t = x % 10;
x /= 10;
if(t == 2 || t == 0 || t == 1 || t == 9)
{
sum += i;
break;
}
}
}
cout << sum << endl;
return 0;
}
2.错误票据 1204
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int a[N];
int n, j;
int main()
{
cin >> n;
//奇怪的输入方式
for(int i = 0; i < n; i++ )
while(cin >> a[j])
j++;
sort(a, a + j);
int res1, res2;
for(int i = 1; i < j; i++ )
if(a[i] >= a[i - 1] + 2)
res2 = a[i - 1] + 1;
else if(a[i] == a[i - 1])
res1 = a[i];
cout << res2 << " " << res1 << endl;
return 0;
}
//stringstream 处理
#include <iostream>
#include <cstring>
#include <algorithm>
#include <sstream>
using namespace std;
const int N = 10010;
int n;
int a[N];
int main()
{
int cnt;
cin >> cnt;
string line;
getline(cin, line);//除回车
for(int i = 0; i < cnt; i++ )
{
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;
}
3.回文日期 466 (枚举 + 模拟)
//枚举日期的话会很麻烦，所以就可以枚举回文数然后判断是不是合法日期
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int day_[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int res;
bool check_valid(int u)
{
int year = u / 10000;
int month = u % 10000 / 100;
int dayday = u % 100;
if(month <= 0 || month > 12) return false;
if(month != 2 && (dayday > day_[month] || dayday <= 0)) return false;
if(month == 2)//特判2月
{
if(year % 100 && year % 4 == 0 || year % 400 == 0)
{
if(dayday <= 0 || dayday > 29)
return false;
}
else if(dayday <= 0 || dayday > 28) return false;
}
return true;
}
int main()
{
int day1, day2;
cin >> day1 >> day2;
for(int i = 1000; i <= 9999; i++ )
{
int day = i, x = i;
//转换成8位回文数
for(int j = 1; j <= 4; j++ ) day = day * 10 + x % 10, x /= 10;
if(day1 <= day && day <= day2)
if(check_valid(day)) res++;
}
cout << res << endl;
return 0;
}
-
排序
1.归并排序 787
//双指针
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
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++ ) a[i] = tmp[j];
}
int main()
{
int n;
cin >> 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;
}
-
习题
1.移动距离 1219
//画图找规律
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int u, m, n;
cin >> u >> m >> n;
m--, n--;
int x1 = m / u, x2 = n / u;
int y1 = m % u, y2 = n % u;
if(x1 % 2) y1 = u - 1 - y1;
if(x2 % 2) y2 = u - 1 - y2;
cout << abs(x1 - x2) + abs(y1 - y2) << endl;
return 0;
}
2.日期问题 1229
枚举所有数字，筛选出合法的日期，接着再筛选出来符合条件的日期
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int a, b, c;
bool check_valid(int year, int month, int day)//检测日期是否合法
{
if(month <= 0 || month > 12) return false;
if(month != 2)
{
if(day <= 0 || day > days[month]) return false;
}
if(month == 2)
{
if(year % 4 == 0 && year % 100 || year % 400 == 0)
{
if(day <= 0 || day > 29) return false;
}
else if(day <= 0 || day > 28) return false;
}
return true;
}
int main()
{
scanf("%d/%d/%d", &a, &b, &c);//格式化输入的优势
for(int i = 19600101; i <= 20591231; i++ )
{
int year = i / 10000, month = i % 10000 / 100, day = i % 100;
if(check_valid(year, month, day))
{
if(year % 100 == a && month == b && day == c || //年月日
day == a && month == b && year % 100 == c || //日月年
month == a && day == b && year % 100 == c //月日年
)
printf("%d-%02d-%02d
", year, month, day);
}
}
return 0;
}
3.航班问题 1231(模拟，数学)
对于这种格式化输入输出的题，应该灵活应用printf， scanf
思路：
规范小时的减法有点难实现，所以不如统一转换成秒数来计算
sscanf的格式化读入非常有效
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int get_seconds(int h, int m, int s)
{
return h * 3600 + m * 60 + s;
}
int get_time()
{
string line;
getline(cin, line);
if (line.back() != ')') line += " (+0)";
int h1, m1, s1, h2, m2, s2, d;
sscanf(line.c_str(), "%d:%d:%d %d:%d:%d (+%d)", &h1, &m1, &s1, &h2, &m2, &s2, &d);
return get_seconds(h2, m2, s2) - get_seconds(h1, m1, s1) + d * 24 * 3600;
}
int main()
{
int n;
scanf("%d", &n);
string line;
getline(cin, line); // 忽略掉第一行的回车
while (n -- )
{
int time = (get_time() + get_time()) / 2;
int hour = time / 3600, minute = time % 3600 / 60, second = time % 60;
printf("%02d:%02d:%02d
", hour, minute, second);
}
return 0;
}
4.外卖店优先级 1241(★★)
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
bool st[N];
int score[N], last[N];
PII order[N];//存放输入数据，好处理
int main()
{
int n, m, T;
cin >> n >> m >> T;
for(int i = 0; i< m; i++ ) scanf("%d%d", &order[i].x, &order[i].second);
sort(order, order + m);
for(int i = 0; i < m;)
{
int j = i;
while(order[i] == order[j] && j < m) j++;//
int t = order[i].x, id = order[i].y, cnt = j - i;
i = j;//
score[id] -= t - last[id] - 1;
if(score[id] < 0) score[id] = 0;
if(score[id] <= 3) st[id] = false;
if(score[id] > 5) st[id] = true;//在此之前处理的是t时刻之前的订单
score[id] += cnt * 2;
if(score[id] > 5) st[id] = true;
last[id] = t;
}
for(int i = 1; i <= n; i++)
{
if(last[i] < T)//如果在last[i]出现过之后没有再有订单的情况
{
score[i] -= T - last[i];
if(score[i] <= 3) st[i] = false;
}
}
int res = 0;
for(int i = 1; i <= n; i++ ) res += st[i];//bool自动转换成int
cout << res << endl;
return 0;
}
5.逆序对的数量 788(归并排序)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int a[N], tmp[N];
long long res;
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++], res += mid - i + 1;
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(i = l, j = 0; i <= r; i++, j++ ) a[i] = tmp[j];
}
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++ ) scanf("%d", a + i);
merge_sort(a, 0, n - 1);
cout << res << endl;
return 0;
}