A Wonderful Permutation
只需要将前k小的数放到前k位即可
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//#define int long long
const int N = 110,M = N * N,INF = 0x3f3f3f3f;
typedef long long LL;
#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
int a[N];
void solve()
{
int n,k;cin >> n >> k;
for(int i = 1; i <= n; i ++)cin >> a[i];
//我们只需要将前k小的数放到前k位即可
int res = 0;
for(int i = 1; i <= k; i ++)
if(a[i] > k)res ++;
cout << res << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
//solve();
return 0;
}
B Woeful Permutation
从大到小考虑每个数,只要两个数互质乘积一定是最大的,详见代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
//#define int long long
#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
//inline int read()
//{
// int x = 0,f = 1; char ch = getchar();
// while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
// while(ch >= '0' && ch <= '9')x = (x << 3) + (x << 1) + ch - '0',ch = getchar();
// return x * f;
//}
//互质
void solve()
{
int n;cin >> n;
if(n & 1)
{
cout << 1 << " ";
for(int i = 2; i <= n; i ++)
cout << (i ^ 1) << " ";
}
else
{
for(int i = 1; i <= n; i += 2)
cout << i + 1 << " " << i << " ";
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
return 0;
}
题意:给定你一个数组,定义一种操作为将所有值为x的数变成0,问最少操作多少次后数组变成
非严格单调递增的
思路:对于一组合法的解,我们要找到最终0和非零的分界线
一个数要变成零,那么他前面的所有的数也要全部变成零才合法,考虑到有重复,所以是其最后一个位置之前的所有数
我们想想看如果只找到最长的不减后缀也是不能满足条件的,因为重复的存在,我们在将前面元素置成0的同时可能会影响到
我们的后缀,所以我们要找到每个至少出现两次且不相邻的数出现的最后位置,这种数从前到所到达的所有位置一定都得是0
这是我们最长后缀的一个限制,在此条件下枚举最长后缀得到最大操作位置即可
核心:发现不相邻的多段之间为零,最长后缀
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
//#define int long long
const int N = 1e5 + 10,INF = 0x3f3f3f3f;
typedef long long LL;
#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
int a[N];
void solve()
{
int n; cin >> n;
for(int i = 1; i <= n; i ++)cin >> a[i];
map<int,int>mp;//用来标记这个数是否出现过
int maxv = 0;//用来找到最远的一个至少出现两次的不相邻的数的位置
for(int i = 1; i <= n; i ++)
{
if(mp[a[i]] && a[i] != a[i - 1])
{
maxv = max(maxv, i);
mp[a[i]] = 1;
}
else mp[a[i]] = 1;
}
//cout << maxv << endl;
//在限制条件下找到最长后缀
for(int i = n; i > maxv + 1; i --)//我们最多到maxv+1的位置
if(a[i] < a[i - 1]) {
maxv = i - 1;
break;
}
//cout << maxv << endl;
map<int,int>m;//判重
int res = 0;
//将前面不合法的置成0
for(int i = 1; i <= maxv; i ++)
{
if(!m[a[i]])res ++;
m[a[i]] = 1;
}
cout << res << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
//solve();
return 0;
}
题意:给定一个n个结点的无向图,定义边权为数组种l->r一段的最小值
我们要求出图的直径,为某两个点之间最短路的最大值
贪心:
两点之间如果是直接到达,一定是最近限制越小取的值越大。
两点之间的最近距离一共有两种情况:
1.直达 a[i]和a[i+1]的最小值
2.经中转点到最小值点 2*minv
我们可以用操作尽可能使得最小值最大,所以可以用k-1次操作使得最小的k-1个数变成正无穷
最后一次操作有两种选择:
(1)使第k小的数变成正无穷
(2)使得a[i]和a[i+1]比较中取到最大的那一个
将这两种操作都做一遍取一个最大值
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int N = 2e5 + 10,INF = 1e9;
typedef long long LL;
#define int long long
typedef pair<int,int>PII;
#define x first
#define y second
PII q[N];
int a[N],b[N];
bool cmp(PII a, PII b)
{
return a.second < b.second;
}
void solve()
{
int n,k;cin >> n >> k;
for(int i = 0; i < n; i ++)cin >> a[i],q[i] = {i, a[i]};
sort(q, q + n, cmp);
//将前k小的数变成正无穷
for(int i = 0; i < k - 1 ; i ++)
{
q[i].second = INF;
a[q[i].first] = INF;
}
for(int i = 0; i < n; i ++)b[i] = a[i];//两种情况
int t = -INF;
a[q[k - 1].first] = INF;//将前k小的全部置成无穷的情况
for(int i = 0; i < n - 1; i ++)
t = max(t, min(a[i], a[i + 1]));
int res1 = 0,res2 = 0;
sort(a, a + n);
res1 = min(a[0] * 2, t);//现在a数组中最小的数和t取一个最小是我们的距离
sort(b, b + n);
//最小数的二倍和最大的数取一个最小
res2 = min(b[0] * 2, b[n - 1]);//剩一种操作,一定能取到最大的数
//两种情况取一个最大就是直径
cout << max(res1,res2) << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
return 0;
}