1089 Insert or Merge (25 分)【难度: 一般 / 知识点: 模拟】
2023-09-11 14:15:52 时间
https://pintia.cn/problem-sets/994805342720868352/problems/994805377432928256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5*3+10;
int n,x,flag;
vector<int>a,b,c;
void solve1()
{
c=a;
for(int i=1;i<n;i++)
{
int j=i;
while(j&&c[j-1]>c[j]) swap(c[j-1],c[j]),j--;
if(c==b)
{
flag=true;
int j=i+1;
while(j&&c[j-1]>c[j]) swap(c[j-1],c[j]),j--;
break;
}
}
}
void solve2()
{
c=a;
for(int i=2;i<=n;i*=2)
{
for(int j=0;j+i<=n;j+=i) sort(c.begin()+j,c.begin()+j+i);
if(n%i) sort(c.begin()+n/i*i,c.end());
if(c==b)
{
i=i*2;
for(int j=0;j+i<=n;j+=i) sort(c.begin()+j,c.begin()+j+i);
if(n%i) sort(c.begin()+n/i*i,c.end());
break;
}
}
}
int main(void)
{
cin>>n;
for(int i=0;i<n;i++) cin>>x,a.push_back(x);
for(int i=0;i<n;i++) cin>>x,b.push_back(x);
solve1();
if(flag) puts("Insertion Sort");
else
{
solve2();
puts("Merge Sort");
}
for(int i=0;i<c.size();i++)
{
cout<<c[i];
if(i+1!=c.size()) cout<<" ";
}
return 0;
}
相关文章
- python爬虫知识点总结(十一)使用Selenium模拟浏览器抓取淘宝商品美食信息
- 2022最全知识点——RF接口自动化框架项目实战
- JS 知识点
- 1112 Stucked Keyboard (20 分)【难度: 一般 / 知识点: 模拟】
- 1105 Spiral Matrix (25 分)【难度: 一般 / 知识点: 模拟】
- 1088 Rational Arithmetic (20 分)【难度: 简单 / 知识点: 模拟】
- 1153 Decode Registration Card of PAT (25 分)【难度: 一般 / 知识点: 排序 模拟】
- 1152 Google Recruitment (20 分)【难度: 简单 / 知识点: 模拟】
- 1142 Maximal Clique (25 分)【难度: 一般 / 知识点: 模拟】
- 1134 Vertex Cover (25 分)【难度: 一般 / 知识点: 模拟】
- 1122 Hamiltonian Cycle (25 分)【难度: 一般 / 知识点: 模拟 哈密顿回路】
- 1121 Damn Single (25 分)【难度: 一般 / 知识点: 哈希表,模拟】
- 1060 Are They Equal (25 分)【难度: 一般 / 知识点: 模拟 字符串处理】
- 1047 Student List for Course (25 分)【难度: 简单 / 知识点: 模拟】
- 1042 Shuffling Machine (20 分)【难度: 简单 / 知识点: 模拟】
- 1039 Course List for Student (25 分)【难度: 一般 / 知识点: 模拟 哈希表】
- 1033 To Fill or Not to Fill (25 分)【难度: 难 / 知识点: 模拟 贪心】
- 1017 Queueing at Bank (25 分) 【未完成】【难度: 中 / 知识点: 模拟】
- 1016 Phone Bills (25 分) 【未完成】【难度: 中 / 知识点: 模拟】
- 1010 Radix (25 分)【难度: 难 / 知识点: 二分查找】
- 1008 Elevator (20 分)【难度: 简单 / 知识点: 模拟】
- 1002 A+B for Polynomials (25 分)【难度: 一般 / 知识点: 模拟】
- 小程序基础知识点讲解-WXML + WXSS + JS,生命周期
- Android开发工程师文集-Android知识点讲解
- BERT相关知识点复盘
- Django知识点
- 计组 | 【六 总线】知识点及例题
- Web测试方面的知识点整理