当前位置:网站首页>Yugu p1020 missile interception (binary search)
Yugu p1020 missile interception (binary search)
2022-07-07 07:59:00 【zjsru_ Beginner】
subject
In order to defend against the missile attack of the enemy , Developing a missile interception system . But there's a flaw in this interceptor system : Although its first shell can reach any height , But in the future, each shell can not be higher than the height of the previous one . One day , The radar caught the enemy's missiles coming . Because the system is still in the trial stage , So there's only one system , So it may not be possible to intercept all missiles .
Enter the Missile Altitude in turn ( The altitude data given by the radar is \le 50000≤50000 The positive integer ), Calculate how many missiles this system can intercept at most , If you want to intercept all missiles, at least how many of these missile interception systems should be equipped .
Input format
1 That's ok , Several integers ( Number \le 100000≤100000)
NOIP The data scale of the original question does not exceed 2000.
Output format
2 That's ok , One integer per row , The first number shows how many missiles the system can intercept at most , The second number indicates the minimum number of such missile interception systems to be equipped if all missiles are to be intercepted .
sample input
389 207 155 300 299 170 158 65
sample output
6 2
Design thinking
This question requires a non rising sequence length and a rising sequence length , Mainly used lower_bound And upper_bound To find out , First create an initial length of 1 Of len1 and len2,d1[1] and d2[1], As in the example above , First the 389 Add to an array , Compare again 389 And the next number 207, obviously 207 smaller , And add it to the array , Continue back until the number 300 when , Cannot be directly added to the array , You must replace the first one in the array that is less than 300 The number of , namely 207. Add and replace many times , It finds out the maximum number of missiles that can be intercepted and the minimum system to be equipped .
The following description follows lower_bound And upper_bound Usage of :
Both of these functions can only be used for ascending sequences , The following example :
int main()
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
cout << (lower_bound(a, a + 12, 4) - a) << endl; // Output 3
cout << (upper_bound(a, a + 12, 4) - a) << endl; // Output 4
}
If the sequence is descending :
int a[] = {4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1};
cout << (lower_bound(a, a + 12, 4) - a) << endl; // Output 12
cout << (upper_bound(a, a + 12, 4) - a) << endl; // Output 12
cout << (lower_bound(a, a + 12, 1) - a) << endl; // Output 0
cout << (upper_bound(a, a + 12, 1) - a) << endl; // Output 0
The code is as follows :
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N], d1[N], d2[N], n;
int main() {
while (cin >> a[++n]); n--;
int len1 = 1, len2 = 1; // The initial length is 1
d1[1] = a[1]; // Used to calculate the length of Non rising sequence
d2[1] = a[1]; // Used to find the length of ascending sequence
for (int i=2; i<=n; i++) { // from a[2] Start enumerating each number
if (d1[len1] >= a[i]) d1[++len1] = a[i]; // If you meet the requirements and don't rise, join d1
else { // Otherwise, use a[i] Replace d1 One of the numbers
int p1 = upper_bound(d1 + 1, d1 + 1 + len1, a[i], greater<int>()) - d1;
d1[p1] = a[i];
}
if (d2[len2] < a[i]) d2[++len2] = a[i];
else {
int p2 = lower_bound(d2 + 1, d2 + 1 + len2, a[i]) - d2;
d2[p2] = a[i];
}
}
cout << len1 << endl << len2;
return 0;
}
Running results :
big data 201 tyx
边栏推荐
- [2022 actf] Web Topic recurrence
- leetcode:105. Constructing binary trees from preorder and inorder traversal sequences
- Detailed explanation of uboot image generation process of Hisilicon chip (hi3516dv300)
- nacos
- Detailed explanation of Kalman filter for motion state estimation
- numpy中dot函数使用与解析
- These five fishing artifacts are too hot! Programmer: I know, delete it quickly!
- misc ez_ usb
- What is the interval in gatk4??
- [UTCTF2020]file header
猜你喜欢
Use and analysis of dot function in numpy
3D reconstruction - stereo correction
Linux server development, SQL statements, indexes, views, stored procedures, triggers
[Stanford Jiwang cs144 project] lab4: tcpconnection
2022 recurrent training question bank and answers of refrigeration and air conditioning equipment operation
Figure out the working principle of gpt3
Few shot Learning & meta learning: small sample learning principle and Siamese network structure (I)
buuctf misc USB
Cnopendata list data of Chinese colleges and Universities
Idea add class annotation template and method template
随机推荐
[CV] Wu Enda machine learning course notes | Chapter 8
【webrtc】m98 screen和window采集
2022焊工(初级)判断题及在线模拟考试
Pytest+allure+jenkins environment -- completion of pit filling
Cnopendata list data of Chinese colleges and Universities
Few-Shot Learning && Meta Learning:小样本学习原理和Siamese网络结构(一)
Resource create package method
芯片资料 网站 易特创芯
[2022 ciscn] replay of preliminary web topics
pytest+allure+jenkins环境--填坑完毕
PHP exports millions of data
Few shot Learning & meta learning: small sample learning principle and Siamese network structure (I)
LeetCode 40:组合总和 II
The configuration that needs to be modified when switching between high and low versions of MySQL 5-8 (take aicode as an example here)
Qt学习28 主窗口中的工具栏
C语言航班订票系统
[P2P] local packet capturing
paddlepaddle 29 无模型定义代码下动态修改网络结构(relu变prelu,conv2d变conv3d,2d语义分割模型改为3d语义分割模型)
[unity] several ideas about circular motion of objects
[webrtc] m98 Screen and Window Collection