Stack
Reverse Polish notation is a notation where every operator follows all of its operands. For example, an expression (1+2)*(5+4) in the conventional Polish notation can be represented as 1 2 + 5 4 + * in the Reverse Polish notation. One of advantages of the Reverse Polish notation is that it is parenthesis-free.
Write a program which reads an expression in the Reverse Polish notation and prints the computational result.
An expression in the Reverse Polish notation is calculated using a stack. To evaluate the expression, the program should read symbols in order. If the symbol is an operand, the corresponding value should be pushed into the stack. On the other hand, if the symbols is an operator, the program should pop two elements from the stack, perform the corresponding operations, then push the result in to the stack. The program should repeat this operations.
Input
An expression is given in a line. Two consequtive symbols (operand or operator) are separated by a space character.
You can assume that +, - and * are given as the operator and an operand is a positive integer less than 106
Output
Print the computational result in a line.
Constraints
2 ≤ the number of operands in the expression ≤ 100
1 ≤ the number of operators in the expression ≤ 99
-1 × 109 ≤ values in the stack ≤ 109
Sample Input 1
1 2 +
Sample Output 1
3
Sample Input 2
1 2 + 3 4 - *
Sample Output 2
-3
题意：给出一个波兰表达式, 计算出结果。波兰表示法: 运算符在数字的后面,例如1 2 + 3 4 - * 就代表(1+2)*(3-4)=-3。
题解：按着题意用栈模拟
#include<iostream>
#include<stack>
using namespace std;
string s;
int main() {
stack<long long> st;
while (cin >> s) {
if (s[0] >= '0' && s[0] <= '9') {
long long num = 0;
for (int i = 0; i < s.length(); i++) {
long long temp = (s[i] - '0');
num = num * 10 + temp;
}
st.push(num);
} else {
long long a, b;
b = st.top();
st.pop();
a = st.top();
st.pop();
if (s[0] == '*')
a = a * b;
else if (s[0] == '+')
a = a + b;
else if (s[0] == '-')
a = a - b;
st.push(a);
if (cin.get() == '\n')
{
break;
}
}
}
long long ans = st.top();
st.pop();
cout << ans << endl;
return 0;
}
Queue
There are n processes in a queue. Each process has namei and timei. The round-robin scheduling handles the processes in order. A round-robin scheduler gives each process a quantum (a time slot) and interrupts the process if it is not completed by then. The process is resumed and moved to the end of the queue, then the scheduler handles the next process in the queue.
For example, we have the following queue with the quantum of 100ms.
A(150) - B(80) - C(200) - D(200)
First, process A is handled for 100ms, then the process is moved to the end of the queue with the remaining time (50ms).
B(80) - C(200) - D(200) - A(50)
Next, process B is handled for 80ms. The process is completed with the time stamp of 180ms and removed from the queue.
C(200) - D(200) - A(50)
Your task is to write a program which simulates the round-robin scheduling.
Input
n q
name1 time1
name2 time2
…
namen timen
In the first line the number of processes n and the quantum q are given separated by a single space.
In the following n lines, names and times for the n processes are given. namei and timei are separated by a single space.
Output
For each process, prints its name and the time the process finished in order.
Constraints
1 ≤ n ≤ 100000
1 ≤ q ≤ 1000
1 ≤ timei ≤ 50000
1 ≤ length of namei ≤ 10
1 ≤ Sum of timei ≤ 1000000
Sample Input 1
5 100
p1 150
p2 80
p3 200
p4 350
p5 20
Sample Output 1
p2 180
p5 400
p1 450
p3 550
p4 800
题意：CPU处理任务，对于每个任务最多只能处理q毫秒,若任务没有处理完，则将任务添加到队列最末尾然后轮到他的时候再次处理
题解：用队列来模拟人物的循环处理
#include<iostream>
#include<stack>
#include<queue>
#include<map>
using namespace std;
queue<pair<string, int>> q;
const int n = 1e5 + 10;
int main(void) {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
pair<string, int> tmp;
cin >> tmp.first >> tmp.second;
q.push(tmp);
}
long long ans = 0;
while (!q.empty()) {
queue<pair<string, int>> qq;
if (q.front().second <= m) {
ans += q.front().second;
cout << q.front().first << " " << ans << endl;
q.pop();
}
else{
ans += m;
q.front().second -= m;
q.push(q.front());
q.pop();
}
}
}
Shaolin
Shaolin temple is very famous for its Kongfu monks.A lot of young men go to Shaolin temple every year, trying to be a monk there. The master of Shaolin evaluates a young man mainly by his talent on understanding the Buddism scripture, but fighting skill is also taken into account.
When a young man passes all the tests and is declared a new monk of Shaolin, there will be a fight , as a part of the welcome party. Every monk has an unique id and a unique fighting grade, which are all integers. The new monk must fight with a old monk whose fighting grade is closest to his fighting grade. If there are two old monks satisfying that condition, the new monk will take the one whose fighting grade is less than his.
The master is the first monk in Shaolin, his id is 1，and his fighting grade is 1,000,000,000.He just lost the fighting records. But he still remembers who joined Shaolin earlier, who joined later. Please recover the fighting records for him.
Input
There are several test cases.
In each test case:
The first line is a integer n (0 <n <=100,000),meaning the number of monks who joined Shaolin after the master did.(The master is not included).Then n lines follow. Each line has two integer k and g, meaning a monk’s id and his fighting grade.( 0<= k ,g<=5,000,000)
The monks are listed by ascending order of jointing time.In other words, monks who joined Shaolin earlier come first.
The input ends with n = 0.
Output
A fight can be described as two ids of the monks who make that fight. For each test case, output all fights by the ascending order of happening time. Each fight in a line. For each fight, print the new monk’s id first ,then the old monk’s id.
Sample Input
3
2 1
3 3
4 2
0
Sample Output
2 1
3 2
4 2
题意：每个和尚根比自己之前进的相近战力的和尚打，找出和尚的比武顺序
题解：每个和尚用map确定位序然后用二分查找和他相近战力的和尚
#include<iostream>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<string>
using namespace std;
const int maxn = 1e9;
int main(void) {
int n;
while (cin >> n && n) {
map<int, int> m;
m[maxn] = 1;
while (n--) {
int k, g;
cin >> k >> g;
map<int, int>::iterator it = m.lower_bound(g);
if (it == m.begin()) cout << k << " " << it->second << endl;
else {
map<int, int>::iterator x = it, y = --it;
if (x->first - g >= g - y->first) {
cout << k << " " << y->second << endl;
} else {
cout << k << " " << x->second << endl;
}
}
m[g] = k;
}
}
}
Equal Sums
You are given k sequences of integers. The length of the i-th sequence equals to ni
.
You have to choose exactly two sequences i
and j (i≠j) such that you can remove exactly one element in each of them in such a way that the sum of the changed sequence i (its length will be equal to ni?1) equals to the sum of the changed sequence j (its length will be equal to nj?1
).
Note that it’s required to remove exactly one element in each of the two chosen sequences.
Assume that the sum of the empty (of the length equals 0
) sequence is 0
.
Input
The first line contains an integer k
(2≤k≤2?105
) — the number of sequences.
Then k
pairs of lines follow, each pair containing a sequence.
The first line in the i
-th pair contains one integer ni (1≤ni<2?105) — the length of the i-th sequence. The second line of the i-th pair contains a sequence of ni integers ai,1,ai,2,…,ai,ni
.
The elements of sequences are integer numbers from ?104
to 104
.
The sum of lengths of all given sequences don’t exceed 2?105
, i.e. n1+n2+?+nk≤2?105
.
Output
If it is impossible to choose two sequences such that they satisfy given conditions, print "NO" (without quotes). Otherwise in the first line print "YES" (without quotes), in the second line — two integers i
, x (1≤i≤k,1≤x≤ni), in the third line — two integers j, y (1≤j≤k,1≤y≤nj). It means that the sum of the elements of the i-th sequence without the element with index x equals to the sum of the elements of the j-th sequence without the element with index y
.
Two chosen sequences must be distinct, i.e. i≠j
. You can print them in any order.
If there are multiple possible answers, print any of them.
Examples
Input
2
5
2 3 1 3 2
6
1 1 2 2 2 1
Output
YES
2 6
1 2
Input
3
1
5
5
1 1 1 1 1
2
2 3
Output
NO
Input
4
6
2 2 2 2 2 2
5
2 2 2 2 2
3
2 2 2
5
2 2 2 2 2
Output
YES
2 2
4 1
Note
In the first example there are two sequences [2,3,1,3,2]
and [1,1,2,2,2,1]. You can remove the second element from the first sequence to get [2,1,3,2] and you can remove the sixth element from the second sequence to get [1,1,2,2,2]. The sums of the both resulting sequences equal to 8, i.e. the sums are equal.
题意：小A有 n 个整数数列 a1,a2,…an ，每个数列的长度为li。
请你找出两个编号不同的数列，并从这两个数列中各恰好删除一个数，使得这两个数列的和相等。
#include<iostream>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<string>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int main(void) {
int n;
cin >> n;
map<long long, pair<int, int>> m;
for (int i = 1; i <= n; i++) {
int nn;
cin >> nn;
long long sum = 0;
for (int j = 1; j <= nn; j++) {
cin >> a[j];
sum += a[j];
}
for (int j = 1; j <= nn; j++) {
if (m.count(sum - a[j]) && m[sum - a[j]].first != i) {
cout << "YES" << endl << m[sum - a[j]].first << " " << m[sum - a[j]].second << endl << i << " " << j;
return 0;
} else {
m[sum - a[j]].first = i;
m[sum - a[j]].second = j;
}
}
}
cout << "NO" << endl;
return 0;
}
Potions (Hard Version)
This is the hard version of the problem. The only difference is that in this version n≤200000
. You can make hacks only if both versions of the problem are solved.
There are n
potions in a line, with potion 1 on the far left and potion n on the far right. Each potion will increase your health by ai when drunk. ai
can be negative, meaning that potion will decrease will health.
You start with 0
health and you will walk from left to right, from first potion to the last one. At each potion, you may choose to drink it or ignore it. You must ensure that your health is always non-negative.
What is the largest number of potions you can drink?
Input
The first line contains a single integer n
(1≤n≤200000
) — the number of potions.
The next line contains n
integers a1, a2, … ,an (?109≤ai≤109
) which represent the change in health after drinking that potion.
Output
Output a single integer, the maximum number of potions you can drink without your health becoming negative.
翻译：
这是问题的硬版本。唯一的区别是在这个版本中≤20万。只有两个版本的问题都解决了，你才能进行黑客攻击。
一行有n种药剂，药剂1在最左边，药剂n在最右边。每一种药剂都会增加你的生命值。ai可以是负的，意味着药剂会降低生命值。
你从0点生命值开始，从左到右，从第一个魔药到最后一个魔药。在每一个药水，你可以选择喝它或忽略它。你必须确保你的健康永远是非负的。
你能喝的药水最多是多少？
（原文链接：https://blog.csdn.net/lalala625/article/details/117380261）
题解：
标准的反悔贪心 用优先队列存一下就ok了
#include<iostream>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<string>
const int N = 2e5 + 10;
using namespace std;
int a[N];
int main(void) {
long long n, x;
cin >> n;
priority_queue<long long, vector<long long>, greater<long long> > q;
long long sum = 0, cnt = 0;
for (int i = 1; i <= n; i++) {
cin >> x;
if (x >= 0) {
sum += x;
cnt++;
} else {
if (sum + x >= 0) {
sum += x;
cnt++;
q.push(x);
} else {
if (q.empty())continue;
else if (x > q.top()) {
sum -= q.top();
sum += x;
q.pop();
q.push(x);
}
}
}
}
cout << cnt << endl;
return 0;
}
Buy and Resell
The Power Cube is used as a stash of Exotic Power. There are n cities numbered 1,2,…,n where allowed to trade it. The trading price of the Power Cube in the i-th city is ai dollars per cube. Noswal is a foxy businessman and wants to quietly make a fortune by buying and reselling Power Cubes. To avoid being discovered by the police, Noswal will go to the i-th city and choose exactly one of the following three options on the i-th day:
- spend ai dollars to buy a Power Cube
- resell a Power Cube and get ai dollars if he has at least one Power Cube
- do nothing
Obviously, Noswal can own more than one Power Cubes at the same time. After going to the n
cities, he will go back home and stay away from the cops. He wants to know the maximum profit he can earn. In the meanwhile, to lower the risks, he wants to minimize the times of trading (include buy and sell) to get the maximum profit. Noswal is a foxy and successful businessman so you can assume that he has infinity money at the beginning.
Input
There are multiple test cases. The first line of input contains a positive integer T (T≤250), indicating the number of test cases. For each test case:
The first line has an integer n. (1≤n≤105)
The second line has n integers a1,a2,…,an where ai means the trading price (buy or sell) of the Power Cube in the i-th city. (1≤ai≤109)
It is guaranteed that the sum of all n is no more than 5×105
.
Output
For each case, print one line with two integers —— the maximum profit and the minimum times of trading to get the maximum profit.
题意：有 n 天，给出每天物品的价格，一个人最初有无限多的钱，每天可以选择买一个物品、卖一个物品或者什么都不做，问这个人的最大收益。
题解：用优先队列维护一下价格查一下最大的收益差
#include<iostream>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<string>
using namespace std;
const int N = 1e5 + 10;
int main(void) {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
long long ans = 0, x;
map<int, int> m;
long long cnt = 0;
priority_queue<int, vector<int>, greater<int> > q;
for (int i = 0; i < n; i++) {
cin >> x;
q.push(x);
if (q.top() < x) {
ans += x - q.top();
cnt++;
if (m[q.top()]) {
m[q.top()]--;
cnt--;
}
m[x]++, q.pop();
q.push(x);
}
}
cout << ans << " " << cnt * 2 << endl;
}
return 0;
}
度度熊正在学习双端队列，他对其翻转和合并产生了很大的兴趣。
初始时有 N 个空的双端队列（编号为 1 到 N ），你要支持度度熊的 Q 次操作。
①1 u w val 在编号为 u 的队列里加入一个权值为 val 的元素。（w=0 表示加在最前面，w=1 表示加在最后面）。
②2 u w 询问编号为 u 的队列里的某个元素并删除它。（ w=0 表示询问并操作最前面的元素，w=1 表示最后面）
③3 u v w 把编号为 v 的队列“接在”编号为 u 的队列的最后面。w=0 表示顺序接（队列 v 的开头和队列 u 的结尾连在一起，队列v 的结尾作为新队列的结尾）, w=1 表示逆序接（先将队列 v 翻转，再顺序接在队列 u 后面）。且该操作完成后，队列 v
被清空。
Input
有多组数据。
对于每一组数据，第一行读入两个数 N 和 Q。
接下来有 Q 行，每行 3~4 个数，意义如上。
N≤150000,Q≤400000
1≤u,v≤N,0≤w≤1,1≤val≤100000
所有数据里 Q 的和不超过500000
Output
对于每组数据的每一个操作②，输出一行表示答案。
注意，如果操作②的队列是空的，就输出?1
且不执行删除操作。
Sample Input
2 10
1 1 1 23
1 1 0 233
2 1 1
1 2 1 2333
1 2 1 23333
3 1 2 1
2 2 0
2 1 1
2 1 0
2 1 1
Sample Output
23
-1
2333
233
23333
提示
由于读入过大，C/C++ 选手建议使用读入优化。
一个简单的例子：
void read(int &x){
char ch = getchar();x = 0;
for (; ch < '0' || ch > '9'; ch = getchar());
for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
题解：用map记录相对位置 之后用双端队列模拟即可
#include<iostream>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<string>
using namespace std;
map<int, deque<int> > a;
void read(int &x) {
char ch = getchar();
x = 0;
for (; ch < '0' || ch > '9'; ch = getchar());
for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
int main() {
int n, m, w;
while (scanf("%d%d", &n, &m) != EOF) {
for (int i = 1; i <= n; i++) a[i].clear();
int ki, u, v;
while (m--) {
read(ki);
if (ki == 1) {
read(u), read(w), read(v);
if (w == 0) a[u].push_front(v);
else a[u].push_back(v);
} else if (ki == 2) {
read(u), read(w);
if (a[u].empty()) {
printf("-1\n");
} else {
if (w == 0) {
printf("%d\n", a[u].front());
a[u].pop_front();
} else {
printf("%d\n", a[u].back());
a[u].pop_back();
}
}
} else {
read(u), read(v), read(w);
if (w) {
a[u].insert(a[u].end(), a[v].rbegin(), a[v].rend()), a[v].clear();
} else a[u].insert(a[u].end(), a[v].begin(), a[v].end()), a[v].clear();
}
}
}
return 0;
}
|