Codeforces 631C Report【其他】
2024-08-27 08:56:56
题意:
给定序列,将前a个数进行逆序或正序排列,多次操作后,求最终得到的序列。
分析:
仔细分析可以想到j<i,且rj小于ri的操作是没有意义的,对于每个i把类似j的操作删去(这里可以用multiset或者直接模拟栈的操作),最后我们会获得一个严格下降的序列即ri>rj && i<j,并且相邻的t不相等。
那么对于ri,ri+1,对[0,ri)进行排序后,又对其子序列[0,ri+1)进行相反的排序,其实只有区间[ri+1,ri−1]]内的数是按照ti规定的排序的,并且不会再改变。所以我们只需要根据ti获取[ri+1,ri−1]]之间的值即可。
那么如何获取呢?在头尾两头设两个指针,如果对应区间要求升序,则用大的数填,否则用小的数填上。
代码:
用multiset做(做题太少第一次用set的erase)
#include <cstdio>
#include<set>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = 200005;
int a[maxn], b[maxn];
typedef pair<int, int>p;
#define fi first
#define se second
multiset<p>ms;
int main (void)
{
int n, m;scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++){
scanf("%d", &a[i]);
b[i] = a[i];
}
int maxr = 0;
int r, t;
multiset<p>::iterator pos;
multiset<p>::iterator rp;
for(int i = 0; i < m; i++){
scanf("%d%d", &t, &r);
p tp = p(r, t);
maxr = max(maxr, r);
rp = ms.begin();
while(rp ->first <= tp.first && rp!=ms.end())
ms.erase(rp++);
ms.insert(tp);
}
sort(b, b + maxr);
int u = maxr - 1, l = 0;
pos = ms.end();
pos--;
int cnt = 0;
while(cnt < ms.size()){
int tmp = pos->se;
cnt++;
if(cnt == ms.size()){
for(int j = (pos->fi) - 1; j >=0; j--){
if(tmp == 1) a[j] = b[u--];
else a[j] = b[l++];
}
}
else{
rp = pos--;
for(int j = (rp->fi) - 1; j >= pos->fi; j--){
if(tmp == 1) a[j] = b[u--];
else a[j] = b[l++];
}
}
}
for(int i = 0; i < n; i++){
printf("%d%c", a[i], i == n - 1?'\n':' ' );
}
return 0;
}
模拟栈的操作
#include <cstdio>
#include<algorithm>
using namespace std;//区间递减且t交叉
const int maxn = 200005;
int a[maxn], b[maxn], t[maxn], r[maxn];
int main (void)
{
int n, m;scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++){
scanf("%d", &a[i]);
b[i] = a[i];
}
int s = 0;
for(int i = 0; i < m; i++){
scanf("%d%d", &t[i], &r[i]);
while(s > 0 && r[i] >= r[s - 1]){
s--;
}
t[s] = t[i], r[s] = r[i]; s++;
}
sort(b, b + r[0]);
int l = r[0] - 1, u = 0;
r[s] = 0;
for(int i = 1; i < s + 1; i++){
for(int j = r[i - 1] - 1; j >= r[i]; j--){
if(t[i - 1] == 2) a[j] = b[u++];
else a[j] = b[l--];
}
}
//for(int i = 0; i < n; i++) printf("%d",b[i]);
for(int i = 0; i < n; i++)
printf("%d%c", a[i], i==n-1?'\n':' ');
return 0;
}
智商捉急。。。。比赛的时候就是想不到怎么保存有意义的操作, 就断定这题是一定是要用到自己没学过的数据结构。。真的要对自己自信呀~~思考思考!!
最新文章
- django开发个人简易Blog—nginx+uwsgin+django1.6+mysql 部署到CentOS6.5
- C#重构之道
- linux下对date和timestamp的互转
- Struts2 标签库讲解
- 用Python作GIS之一:介入STARS
- ProtoBuffer 简单例子
- <; IOS >; 论苹果数据持久化。
- Html 小插件9 腾讯新闻
- struts2-----新建项目
- jQuery系列 第八章 jQuery框架Ajax模块
- 阿里云手动安装特定版本的nginx
- throw和throws的区别以及try,catch,finally在有return的情况下执行的顺序
- Linux centos 推拉、共享、监控的设置的分享
- Python中变量的基本使用
- iOS 图像处理(一):获取某一点位置的像素
- python基础(12)-包的导入&;异常处理
- IDEA的maven项目中 静态文件编译的问题
- [ 转载 ]学习笔记-svn用法详解
- 你真的了解HTML吗?–雅虎面试题
- Ionic3环境搭建及创建
热门文章
- 用unsigned char 表示字节
- git ---匿名分支和checkout命令
- 短视频SDK简单易用——来自RDSDK.COM
- nginx教程从入门到精通
- [分享] IMX6嵌入式开发板linux QT挂载U盘及TF卡
- Relational Algebra 关系代数
- 在死循环中使用Scanner获得键盘输入
- createuser - 定义一个新的 PostgreSQL 用户帐户
- html嵌入pdf &;&; html嵌入多媒体文件,word,flash,pdf,音视频
- vue 选项卡