做网站的赢利点,成都网站建设互联,电子商务平台及核心技术,泛微oa办公系统官网一道好题应该有一个简洁的题面。 有一个长度为 n#xff0c;初始全为 0 的序列 a#xff0c;另有一个长度为 n 的序列 b#xff0c;你希望将 a 变成 b#xff0c;你可以执行如下两种操作#xff1a;
1 x#xff1a;将 a 中所有值为 x 的数 11。 2 x#xff1a;将 a 中下…一道好题应该有一个简洁的题面。 有一个长度为 n初始全为 0 的序列 a另有一个长度为 n 的序列 b你希望将 a 变成 b你可以执行如下两种操作
1 x将 a 中所有值为 x 的数 11。 2 x将 a 中下标为 x 的数 11。
你不需要最小化操作次数但只能使用最多 2000020000 次操作。
Input 第一行 一个正整数 n1≤n≤1000。 第二行 n 个非负整数 b1 ,⋯,bn 0≤ bi ≤n描述序列 b。
Output 第一行一个整数 k 表示操作次数你需要保证 0≤k≤20000。 之后 k 行每行两个整数 ,1 x 或 2 x表示一次操作。对于 1 x 类型的操作你需要保证 0≤x≤n对于 2 x 类型的操作你需要保证 1≤x≤n。
Input 4 2 4 3 1
Output 7 1 0 2 1 2 2 2 3 2 2 1 3 2 3
解析
考虑分治将所有相等的数压在一起先然后每次让后半截先 1 然后就可以提出后半截变成子问题了。做完后半截再做前半截。 这样大概是 nlogn 次。 要先进行 后半截的操作避免 1类型操作。
这样造成的效果就是 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 1 2 2 1 2 2 1 1 1 3 3 1 3 3 1 1 1 3 4 1 4 3 1 1 2 3 4 2 4 3 1 (排序后) (原序列) #include bits/stdc.h
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pairint,int PII;
const int N2e610;
vector PII a;
vector PII ans;
int n;
void dfs(int l,int r,int now)
{if (lr) return ;if (lr){while (nowa[l].first){ans.push_back({2,a[l].second});now;}return ;}else{while (nowa[l].first){ans.push_back({1,now});now;}int midlr1;mid;while (midra[mid].firstnow) mid;if (midr){for (int imid;ir;i) ans.push_back({2,a[i].second});dfs(mid,r,now1);dfs(l,mid-1,now);}}
}
signed main()
{ios;cinn;for (int i1;in;i){int x;cinx;a.push_back({x,i});}sort(a.begin(),a.end());dfs(0,a.size()-1,0);coutans.size()endl;for (auto x:ans) coutx.first x.secondendl;return 0;
}
