codeforces 873 D. Merge Sort(分治)
2024-09-01 07:03:02
题目链接:http://codeforces.com/contest/873/problem/D
题解:这题挺简单的,除了一开始算作是调用到一次,然后每次执行操作时都会调用2次,所以最多调用几次就很好算了,而且只有奇数调用次数才合理。然后就是类似分治的思想,每次dfs二分过去,发现调用次数不够就交换mid和mid-1那么就会再被调用2次。
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
using namespace std;
const int M = 1e5 + ;
int a[M] , cnt , n , k , tot;
void dfs(int l , int r) {
if(l == r - ) return ;
if(cnt == k) return ;
int mid = (l + r) >> ;
swap(a[mid] , a[mid - ]);
cnt += ;
dfs(l , mid);
dfs(mid , r);
}
void get_tot(int l , int r) {
int mid = (l + r) >> ;
if(l == r - ) return ;
tot += ;
get_tot(l , mid);
get_tot(mid , r);
}
int main() {
scanf("%d%d" , &n , &k);
for(int i = ; i < n ; i++) a[i] = i + ;
tot = ;
get_tot( , n);
if(k % && k <= tot) {
cnt = ;
dfs( , n);
for(int i = ; i < n ; i++) {
printf("%d " , a[i]);
}
puts("");
}
else {
printf("-1\n");
}
return ;
}
最新文章
- MongoDB学习笔记六—查询下
- WIN32 API编程之 tap顺序
- 建立Maven工程时出错,Failure to transfer com.thoughtworks.xstream:xstream:jar:1.3.1
- CentOS 5/6.X 使用 EPEL YUM源
- vss的ss.ini丢失或损坏导致的vss无法登录错误
- udev:renamed network interface eth0 to eth1
- Application 可以存储全局变量
- JDBC 异常特殊原因 (数据库只读解决办法)
- Oracle学习(十):视图,索引,序列号,同义词
- MyBatis延迟加载和缓存
- python 基础部分重点复习整理2
- HTTPS请求
- vue双向绑定的简单实现(原创)
- C#使用反射获取对象变化的情况
- spring-boot-starter大力出奇迹
- npm无响应处理办法
- mysql [assword expired
- AXURE 8弄一个轮播图的步骤
- Python2 - 基础2 - 数据类型和模块
- RPC笔记之初探RPC:DIY简单RPC框架
热门文章
- Docker 容器高级操作[Docker 系列-3]
- java 8中新的日期和时间API
- 并发知识(2)——关于Thread
- python3学习-Queue模块
- 分享一个非常好用又好看的终端工具--Hyper (支持windows、MacOS、Linux)
- linux100day(day4)--文本处理三剑客
- Flutter学习笔记(16)--Scaffold脚手架、AppBar组件、BottomNavigationBar组件
- 提取html内的文字1
- python案例:实现一个函数版的名片管理系统
- 【JS档案揭秘】第四集 关于this的讨论到此为止