C - Merge the balls
Time Limit: 2 sec / Memory Limit: 1024 MB
Score 250 points
Problem Statement
You have an empty sequence and 𝑁N balls. The size of the 𝑖i-th ball (1≤𝑖≤𝑁) is 2^A[i]
You will perform N operations.
In the 𝑖i-th operation, you add the 𝑖i-th ball to the right end of the sequence, and repeat the following steps:
- If the sequence has one or fewer balls, end the operation.
- If the rightmost ball and the second rightmost ball in the sequence have different sizes, end the operation.
- If the rightmost ball and the second rightmost ball in the sequence have the same size, remove these two balls and add a new ball to the right end of the sequence with a size equal to the sum of the sizes of the two removed balls. Then, go back to step 1 and repeat the process.
Determine the number of balls remaining in the sequence after the N operations.
Constraints
- 1≤𝑁≤2×105
- 0≤Ai≤109
- All input values are integers.
Input
The input is given from Standard Input in the following format:
𝑁 A1 𝐴2 …… 𝐴𝑁
Output
Print the number of balls in the sequence after the 𝑁 operations.
Sample Input 1Copy
Copy
7 2 1 1 3 5 3 3
Sample Output 1Copy
Copy
3
Sample Input 2Copy
Copy
5 0 0 0 1 2
Sample Output 2Copy
Copy
4
思路:
这道题利用动态数组vector来模拟题目的要求,其中需要注意的是vector数下标是从0 开始的,因此判断最右面的元素和倒数第二个右面元素的时候要注意其下标,再就是注意它放入的数据是2 的A[i]的次幂。其他只要掌握vector数组的使用方法,会vector.pop_back,应该就没问题了。
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
void solve()
{
int n; cin>>n;
vector<int> vec;
while(n--)
{
int x; cin>>x;
vec.push_back(x);
while(vec.size()>=2 && (vec[vec.size()-2]==vec[vec.size()-1]) )
{
int x=vec[vec.size()-1];
vec.pop_back();
vec.pop_back();
vec.push_back(x+1);
}
}
cout<<vec.size();
}
int main()
{
int t=1; //cin>>t;
while(t--)
{
solve();
}
return 0;
}