许可优化
软件
产品
贪心
给定一个长度为n的数组 num_1,num_2,num_3 \dots num_n
问是否有两个长度为 n的全排列 p， q满足
num[i]=max(p[i],q[i])
若有输出YES并打印数组
若没有输出NO
特判
首先包括以下几种特判
常规
考虑贪心，先对数组进行排序
上下两个排列，用set来存储还可以使用的值
遍历数组如下:
每一个数 num[i]让下面的先选
其实上下无所谓，先让一方选即可
NO
选中下方代码如下，选中上方则 ab 反一下
ansb[i]=num[i];//下方选num[i]
sb.erase(num[i]);//下方待选列表删除num[i]
ansa[i]=*sa.begin();//上方选待选列表最小值
sa.erase(sa.begin());//上方待选列表删除最小值
注意
排完序后，位置i不再是原来的位置i
所以这里用一个结构体存储值和下标再复制
ansb[num[i].id] = num[i].v;
sb.erase(num[i].v);
ansa[num[i].id] = *sa.begin();
sa.erase(sa.begin());
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 201000
using namespace std;
int ansa[N];
int ansb[N];
struct node
{
int v;
int id;
} num[N];
bool cmp(node a, node b)
{
return a.v < b.v;
}
void solve()
{
int n;
cin >> n;
set<int> sa, sb;
map<int, int> mp;
bool f = true;
for (int i = 1; i <= n; i++)
{
cin >> num[i].v;
num[i].id = i;
sa.insert(i);
sb.insert(i);
mp[num[i].v]++;
if (mp[num[i].v] > 2)
{
f = false;
}
}
/* 特判 */
if (mp[1] > 1 || mp[n] == 0 || f == false)
{
cout << "NO\n";
return;
}
sort(num + 1, num + 1 + n, cmp);
for (int i = 1; i <= n; i++)
{
if (sb.find(num[i].v) != sb.end()) // 选下面的
{
ansb[num[i].id] = num[i].v;
sb.erase(num[i].v);
ansa[num[i].id] = *sa.begin();
sa.erase(sa.begin());
}
else if (sa.find(num[i].v) != sa.end()) //选上面的
{
ansa[num[i].id] = num[i].v;
sa.erase(num[i].v);
ansb[num[i].id] = *sb.begin();
sb.erase(sb.begin());
}
else //都选不到无解
{
cout << "NO\n";
return;
}
}
cout << "YES\n";
for (int i = 1; i <= n; i++)
{
cout << ansa[i] << " ";
}
cout << "\n";
for (int i = 1; i <= n; i++)
{
cout << ansb[i] << " ";
}
cout << "\n";
}
signed main()
{
ios;
int T;
T = 1;
cin >> T;
while (T--)
{
solve();
}
}
置换群 不会
明天会了再更
技术文档
热门文章
155-2731-8020
