前言
有思路就能AC的感觉太爽了。
第一题
题目： Math Problem
题意：
给我们n个区间，找到一个最短的区间，将所有的区间连在一起（换句话说就是找到的区间和所有的区间都有共同的点）。所找到的区间长度可以为0，即只有一个点。
输入格式
输入包含多个样例，第一行是一个整数t，表示有t个样例。
每个样例第一行是一个整数n，表示有n个区间。
每个样例第2到n+1行每行是两个整数l和r，表示区间的左右端点。
输出格式
输出一个整数，表示区间的长度。
数据范围
1 ≤ t ≤ 100
1 ≤ n ≤ 105
1 ≤ li ≤ ri ≤ 109
数据保证所有的n总和不超过1×105
输入样例：
4
3
4 5
5 9
7 7
5
11 19
4 17
16 16
3 12
14 17
1
1 10
1
1 1输出样例：
2
4
0
0思路：
- 贪心。
每次遇到贪心我都不知道是怎么做出来的，迷迷糊糊的，完全凭感觉走，感觉这么做能AC于是就AC了。 - 将所有区间按右端点（即结束端点）升序排序。
- 将第一个区间的右端点记为max_r，从第二个区间开始遍历，每当第i个区间的左端点大于当前的max_r时，就更新max_r。
- 最后输出
max_r - p[1].second。 - 贪心题做的越多越佩服yxc，讲贪心题都要当场证明。会做题只能说明很牛，但是和我有什么关系呢，自己会还能教会别人的才是大佬。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
bool cmp(pair<int, int>a, pair<int, int>b)
{
return a.second < b.second;
}
int main()
{
int t;
cin >> t;
while (t--)
{
cin >> n;
pair<int, int>p[N];
for (int i = 1; i <= n; ++i)
{
cin >> p[i].first >> p[i].second;
}
sort(p + 1, p + n + 1, cmp);
int l = p[1].second;
for (int i = 2; i <= n; ++i)
{
l = max(l, p[i].first);
}
cout << l - p[1].second << endl;
}
return 0;
}第二题
题目： Box
题意：
给我们一个长度为n的序列，要求我们根据给定的序列构建一个长度为n的序列，由数字1n构成，不能有重复的数字。所构建的序列前i个数的最大值要等于给定数列的第i个数qi~。如果所给数列无法构造输出-1。
输入格式
输入包含多个样例，第一行是一个整数t，表示有t个样例。
每个样例第一行是一个整数n，表示给定的数列有n个数。
每个样例第二行是n个整数。
输出格式
如果能够构造出来，将所构造的数列输出，每个数字用空格间隔，否则输出-1。每个样例占一行。
数据范围
1 ≤ t ≤ 104
1 ≤ n ≤ 105
1 ≤ qi ≤ n
保证所给的样例是非下降数列，并且所有的n总和不超过1×105
输入样例：
4
5
1 3 4 5 5
4
1 1 3 4
2
2 2
1
1输出样例：
1 3 4 5 2
-1
2 1
1 思路：
- 用数组a存给定的数列，数组b存构建的数列，数组p记录1~n哪些数被加入到b数组中。
- 首先由于我们构建的数列不能有重复的数字，并且所给定的数列是非下降的，那么就可以得出，如果
a[i]<i一定是无解的，例如给定的数列第3个数是2，我们是无法构建出前三个数中最大值是2的数列的。而只要满足对于任意的i，都有a[i]>=i，那么一定有解。 - 我们可以将所要构建的数组视为一个集合b，集合b初始时为空，遍历所给定的数列a来向集合b中添加数字。
- 我们用数组p来记录1~n中哪些数已经被我们加入到所构建的数组b中。当我们遍历所给数列a时，如果a[i]还没有被添加到b中，那么就直接加入，否则将当前未被添加的最小的数加入到集合b中。
- 因为如果是第一次遇到a[i]，说明a[i]是大于当前b集合中
i-1个数的，所以我们直接将a[i]加入到b集合中。如果此时a[i]已经被加入，说明a[i]小于集合b中的某些数，那么我们直接将当前未放入的最小的数加入集合b中就好了。 - 这里就有一个问题，怎么找到当前最小的数，如果每次都遍历p数组，最坏情况下时间复杂度是O(n2)的，而n的范围最大是105，也就是100亿的级别，一定会超时。我们可以用一个变量j来记录当前的最小值，每次加入集合b中一个数就判断一下j是否已经被加入集合，是的话就让j=j+1，这样时间复杂度就是O(n)，只用遍历一遍就可以。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N];//a存给定的数列，b存构建的数列
bool p[N];//p[i]表示数字i是否已经加入到所构建的数列中
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n;
scanf("%d", &n);
int flag = 0;
for (int i = 1; i <= n; ++i)p[i] = 0;
for (int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
if (a[i] < i)flag = 1;
}
if (flag)
{
cout << -1 << endl;
continue;
}
flag = 0;
int j = 1;
for (int i = 1; i <= n; ++i)
{
if (p[a[i]]==0)
{
b[i] = a[i];
p[a[i]] = 1;
}
else
{
b[i] = j;
p[j] = 1;
}
while (p[j])j++;
}
for (int i = 1; i <= n; ++i)printf("%d ", b[i]);
printf("\n");
}
return 0;
}第四题
题目： Optimal Subsequences (Easy Version)
题意:
给我们一个长度为n的数列，然后是m次询问，每次询问给两个数k和pos，要求我们在给定的数列中找到长度是k的子序列中找到所有元素和最大的子序列，然后在找到的子序列中找到字典序最小的序列，然后在字典序最小的序列中找到第pos个数并输出。
输入格式
输入第一行是一个整数n。
输入第二行是n个整数a1 ~ an，表示整个数列。
第三行是一个整数m。
接下来第4到m+4行是m次询问，每次询问给两个整数k和pos。
输出格式
输出一个整数。
数据范围
1 ≤ n ≤ 100
1 ≤ ai ≤ 109
1 ≤ m ≤ 100
1 ≤ k ≤ n, 1 ≤ posj ≤ kj
输入样例：
3
10 20 10
6
1 1
2 1
2 2
3 1
3 2
3 3输出样例：
20
10
20
10
20
10思路：
- 因为所给的m和n范围都很小，所以我们可以提前将长度1~n的所有子序列中值最大，且字典序最小的序列存下来，每次询问时直接输出就好了。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<cstring>
using namespace std;
const int N = 1e2 + 10;
bool cmp(int a, int b)
{
return a > b;
}
int a[N];
int b[N][N];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);
int c[N];
for (int i = 1; i <= n; ++i)c[i] = a[i];
sort(c + 1, c + n + 1,cmp);
for (int i = n; i >=1 ; --i)
{
int k = 1;
for (int j = 1; j <= n && k <= i; ++j)
{
if(a[j])b[i][k++] = a[j];
}
for (int j = n; j >= 1; --j)
{
if (a[j] == c[i])
{
a[j] = 0;
break;
}
}
}
int m, k, p;
cin >> m;
while (m--)
{
cin >> k >> p;
cout << b[k][p] << endl;
}
return 0;
}
