当前位置:网站首页>Draw Your Cards
Draw Your Cards
2022-07-31 02:10:00 【Yamanaka Ichifusu】
Original link
topic description
The existing n cards are stacked together, each time one card is taken from the top (the value above is x), and placed face up on the table, the placement rules are:
Find the first >=x card already on the table, stack it on top (update the value there)
If it finds a card that meets the requirements every day, open a new pile (single card)
If the number of cards revealed in a certain pile reaches k, this pile can be taken away
In the order of card number 1-n, output when the card was taken, and output -1 for cards that were not taken away
Sample input
5 23 5 2 1 4
Sample output
433-14
Algorithms
(chain storage + binary search)
Simulation.set maintains the number of cards in each pile and the value of the top card
binary search value to achieve update
There is a point that is not very easy to deal with, that is, how to find the path when taking k cards?
Then you can use an array to iterate and save the path (a bit like a linked list, look back)
And because the cards are taken in order, they can be processed online
Note: Use the lower_bound that comes with the set, which is much more efficient than the lower_bound of the
C++ code
Time Complexity O ( n l o g n ) O(nlogn) O(n
#include #include #include #include #include using namespace std;typedef pair PII;int main(){int n,k;scanf("%d%d",&n,&k);vector card(n + 10,-1),cnt(n + 10,0),store(n + 10,-1);set s;for (int i = 1; i <= n; i ++ ) {int p;scanf("%d",&p);auto key = s.upper_bound(p);//Be sure to use the upper_bound that comes with the setif (key == s.end()) {//end is the next to the lasts.insert(p);cnt[p] = 1;}else {//Only the top value is stored, and the pointer is used to store the following valuestore[p] = (*key);cnt[p] = cnt[(*key)] + 1;s.erase(key);s.insert(p);}if (cnt[p] == k) {s.erase(p);int x = p;for(int j = 0;j < k;j++){card[x] = i;x = store[x];//Iterate over the stored values below}}}for (int i = 1;i <= n;i ++ ) printf("%d\n",card[i]);return 0;}
边栏推荐
- mmdetection训练一个模型相关命令
- What is the ideal college life?
- multiplayer-hlap 包有问题,无法升级的解决方案
- PDF split/merge
- [1154]如何将字符串转换为datetime
- Tower of Hanoi problem
- Arbitrum Interview | L2 Summer, what does the standout Arbitrum bring to developers?
- The comprehensive result of the case statement, do you know it?[Verilog Advanced Tutorial]
- [1153] The boundary range of between in mysql
- 软件测试缺陷报告---定义,组成,缺陷的生命周期,缺陷跟踪产后处理流程,缺陷跟踪处理流程,缺陷跟踪的目的,缺陷管理工具
猜你喜欢
ShardingJDBC基本介绍
Static route analysis (the longest mask matching principle + active and standby routes)
GCC Rust获批将被纳入主线代码库,或将于GCC 13中与大家见面
图像处理技术的心酸史
What level of software testing does it take to get a 9K job?
uniapp uses 3rd party fonts
AI在医疗影像设备全流程应用
How to design the changing system requirements
Nacos
Shell script to loop through values in log file to sum and calculate average, max and min
随机推荐
最高月薪20K?平均薪资近万...在华为子公司工作是什么体验?
[1153] The boundary range of between in mysql
Validate XML documents
[WeChat applet] This article takes you to understand data binding, event binding, event parameter transfer, and data synchronization
The comprehensive result of the case statement, do you know it?[Verilog Advanced Tutorial]
f.grid_sample
Verify the integer input
mysql 视图
leetcode-399:除法求值
uniapp使用第三方字体
The effective square of the test (one question of the day 7/29)
什么是理想的大学生活?
Path and the largest
【Map与Set】之LeetCode&牛客练习
MySql installation and configuration super detailed tutorial and simple method of building database and table
934. 最短的桥
英特尔软硬优化,赋能东软加速智慧医疗时代到来
After reading "MySQL Database Advanced Practice" (SQL Xiao Xuzhu)
怎样做好一个创业公司CTO?
leetcode-399: division evaluation