#include<iostream>
#include<vector>
using namespace std;
//升序函数
void acsceding(int* src, int low, int high)
{
if (low < high)
{
int i = low, j = high, temp = src[low];
while (i < j)
{
while ((i < j) && (src[j] >= temp))
{
j--;
}
if (i < j)
{
src[i++] = src[j];
}
while ((i < j) && (src[i] < temp))
{
i++;
}
if (i < j)
{
src[j--] = src[i];
}
}
src[i] = temp;
acsceding(src, low, i - 1);
acsceding(src, i + 1, high);
}
}
//降序函数
void desceding(int* src, int low, int high)
{
if (low < high)
{
int i = low, j = high, temp = src[low];
while (i < j)
{
while ((i < j) && (src[j] < temp))
{
j--;
}
if (i < j)
{
src[i++] = src[j];
}
while ((i < j) && (src[i] >= temp))
{
i++;
}
if (i < j)
{
src[j--] = src[i];
}
}
src[i] = temp;
desceding(src, low, i - 1);
desceding(src, i + 1, high);
}
}
//反序函数
void reverse(int* src, int len)
{
int i = 0, j = len, temp;
while (i < j)
{
temp = src[i];
src[i++] = src[j];
src[j--] = temp;
}
}
int main()
{
//1.读取输入数据
int n, m;
cin >> n >> m;
int* src = new int[n];
for (int i = 0; i < n; i++)
{
cin >> src[i];
}
vector<vector<int>> op(m, vector<int>(2));
for (int i = 0; i < m; i++)
{
cin >> op[i][0] >> op[i][1];
}
//2.找到有效的排序命令
int tempacs = op[0][1], tempacsloc = 0;
int tempdes = op[0][1], tempdesloc = 0;
for (int i = 1; i < m; i++) {
if ((op[i][0] == 1) && (op[i][1] >= tempacs))
{
tempacs = op[i][1];
tempacsloc = i;
}
else if ((op[i][0] == 2) && (op[i][1] >= tempdes))
{
tempdes = op[i][1];
tempdesloc = i;
}
}
//3.如果先升后降,升少降多则选降;先升后降,升多降少则先升后降;……
if (tempacsloc > tempdesloc)
{
if (tempacs >= tempdes)
{
acsceding(src, 0, op[tempacsloc][1] - 1);
}
else {
desceding(src, 0, op[tempdesloc][1] - 1);
reverse(src, tempacs - 1);
}
}
else {
if (tempacs < tempdes)
{
desceding(src, 0, op[tempdesloc][1] - 1);
}
else {
acsceding(src, 0, op[tempacsloc][1] - 1);
reverse(src, tempdes - 1);
}
}
//4.输出
for (int i = 0; i < n; i++)
{
cout << src[i] << " ";
}
}
全部评论
(0) 回帖