https://www.hackerrank.com/contests/101hack46/challenges/lena-sort

把题目转换成一颗二叉树,也就是当前的节点是cur,然后大的,放右边,小的,放左边。

然后所有节点的深度总和,就是答案c。现在就是要你构造一颗这样的树。

最大的树就是左偏树,然后从最后一个节点开始模拟,如果它放移上一格,贡献就会 - 1,所以肯定能构造出一颗满意的树。

至于细节比较多,慢慢debug把。代码也非常混乱。

数据

15 18

7 12

主要是理解为什么这样就是答案。

其实每一个节点的贡献,就是路径的长度,路径的长度表示它被比较了多少次。

一直都是和它的祖先比较。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset> const int maxn = 1e5 + ;
vector<int>G[maxn];
int findmin(int len) {
if (len == ) return ;
if (len == ) return ;
return (len - ) * ;
}
LL findmax(int len) {
return 1LL * len * (len - ) / ;
}
struct node {
int cnt, deep;
node(int a, int b) : cnt(a), deep(b) {}
};
queue<struct node> que;
int val;
int ans[maxn];
void show(int id) {
if (G[id].size() == ) {
ans[id] = val;
// cout << val << " ";
++val;
return;
}
show(G[id][]);
ans[id] = val;
// cout << val << " ";
++val;
if (G[id].size() == ) {
show(G[id][]);
}
}
int check(vector<int> arr) {
if (arr.size() <= ) return ;
vector<int> les;
vector<int> big;
for (int i = ; i < arr.size(); ++i) {
if (arr[i] > arr[]) big.push_back(arr[i]);
else les.push_back(arr[i]);
}
return check(les) + check(big) + arr.size() - ;
}
int len, c;
void bfs(int cur) {
queue<int>que;
que.push(cur);
// vector<int>t;
while (!que.empty()) {
int now = que.front();
que.pop();
cout << ans[now] << " ";
// t.push_back(ans[now]);
for (int i = ; i < G[now].size(); ++i) {
que.push(G[now][i]);
}
}
// if (check(t) != c) {
// cout << "NO" << endl;
// } else cout << "YES" << endl;
}
int deep[maxn];
void work() {
cin >> len >> c;
if (c > findmax(len)) {
cout << - << endl;
return;
}
LL cur = findmax(len);
for (int i = ; i <= len; ++i) {
G[i].clear();
if (i != len) {
G[i].push_back(i + );
}
deep[i] = i - ;
}
while (!que.empty()) que.pop();
que.push(node(, ));
int impo = ;
for (int i = len; i >= && cur > c; --i) {
struct node t = que.front();
int one = i - t.deep - ;
int to = min(cur - c, one * 1LL);
if (to <= ) {
cout << - << endl;
return;
}
if (one == to) {
G[t.cnt].push_back(i);
deep[i] = deep[t.cnt] + ;
G[i].clear();
G[i - ].clear();
if (G[t.cnt].size() == ) {
if (t.cnt == impo) impo++;
que.pop();
que.push(node(G[t.cnt][], t.deep + ));
que.push(node(G[t.cnt][], t.deep + ));
}
} else {
G[i].clear();
G[i - ].clear();
for (int j = ; j <= len; ++j) {
if (deep[i] == deep[j] + to + ) {
G[j].push_back(i);
break;
}
}
break;
}
cur -= to;
}
val = ;
show();
bfs();
// vector<int> t;
// for (int i = 1; i <= len; ++i) {
// cout << ans[i] << " ";
// t.push_back(ans[i]);
// }
// cout << "****" << check(t);
cout << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}

最新文章

  1. Spring 依赖注入控制反转实现,及编码解析(自制容器)
  2. WEB安全--业务安全漏洞
  3. u Calculate e 分类: HDU 2015-06-19 22:18 14人阅读 评论(0) 收藏
  4. 目前比较全的CSS重设(reset)方法总结
  5. gcviewer待整理
  6. AS3 Graphics 多次绘制
  7. 正式学习 react(三)
  8. 为异常处理做准备,熟悉一下WinDbg工具
  9. ABP文档笔记系列
  10. python的map
  11. CentOS配代理服务器
  12. [Swift]LeetCode224. 基本计算器 | Basic Calculator
  13. 第三篇 request篇
  14. uva10256(计算几何)
  15. jQuery设置元素的readonly和disabled属性
  16. javascript,object,IDispatchEx笔记
  17. TinyHttpd代码解析
  18. apache源码安装
  19. 『Scrapy』爬取腾讯招聘网站
  20. jdk5新特性

热门文章

  1. IPython与Jupyter notebook 安装与配置,插件扩展,主题,PDF输出
  2. Redis管理key命令
  3. ufldl学习笔记与编程作业:Logistic Regression(逻辑回归)
  4. bash builtin eval
  5. caioj1272&amp;&amp;codeforces 148D: 概率期望值3:抓老鼠
  6. HDU4081 Qin Shi Huang&#39;s National Road System —— 次小生成树变形
  7. 使用C#开发HTTP服务器系列之Hello World
  8. BZOJ1854:游戏(二分图匹配)
  9. 13_传智播客iOS视频教程_OC程序的编译链接
  10. 关于ArcGis for javascrept之FeatureLayer类与GraphicsLayer类