Bessie slowed down her pace

Table of contents: Algorithm Diary

Bessie slowed down her pace

Topic describes

Bessie the cow is competing in cross-country skiing at the Winter Moo Games.

She set off at 111 meters per second.

But as time went on and she became more and more tired, she began to slow down.

Each time she slowed down, Bessie’s speed dropped: once she slowed down, she moved 1/21/21/2 metres per second, twice she moved 1/31/31/3 metres per second, and so on.

You will be told when and where Bessie will slow down.

When deceleration information is in the following format:

T 17
Copy the code

That means Bessie is slowing down at some point, in this case 171,717 seconds into the race.

When deceleration information is in the following format:

D 10
Copy the code

That means Bessie is slowing down at some point, in this case at 101,010 meters.

Given NNN deceleration messages, calculate how many seconds it will take Bessie to finish a kilometer.

Round your answer to the nearest whole number (round up to 111).

Input format

The first line contains the integer NNN.

NNN lines follow, each describing a deceleration message in the format T x or D x.

In either case, XXX is an integer, ensuring that all decelerations occur a kilometer before Bessie finishes skiing.

There could have been multiple decelerations at the same time, which would have made Bessie go much slower all at once.

All deceleration information is not necessarily given in order.

The output format

Output the total time Bessie needed to ski a kilometer.

Data range

$1 N 10000 or less or less$

Enter the sample

2
T 30
D 10
Copy the code

The output sample

2970
Copy the code

Algorithm ideas

If only time or place deceleration is considered, the calculation can be done by sorting the corresponding sequence. What’s hard to deal with here is both time deceleration and place deceleration. Single sequence is easy to process, so it is considered whether time series and place series can be combined, and it is necessary to ensure that the sorted sequence is still in ascending order from the point of view of time and place.

Therefore, we set the current location as SSS and the current time as TTT. In order to ensure that THE size of SSS and TTT can be compared, VVV speed is introduced. Since the speed VVV in the question decreases by 1/(1+ N)1/(1+ N)1/(1+ N)1/(1+ N) (n is the deceleration times) from 111, we take VVV as the reciprocal of speed, let a[I] represent time series, b[j] represent place series, The point nearest to the current position (SSS and TTT represent the same position and are updated at the same time) decelerates first, so as to take time as the unit of measurement, then:

According to the above size relation, two-way merge is carried out.

AC code

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> a, b;
int n;
char op;
int x;
int main(a) {
    cin>>n;
    while(n--) {
        cin>>op>>x;
        if(op == 'T') a.push_back(x);
        else b.push_back(x);
    }
    b.push_back(1000);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    double s = 0;
    double t = 0;
    double v = 1;
    
    int i = 0;
    int j = 0;
    while(i < a.size() || j < b.size()) {
        if(j == b.size() || i < a.size() && a[i] - t < (b[j] - s) * v) {
            s += (a[i] - t) / v;
            t = a[i];
            i += 1;
            v += 1;
        } else {
            t += (b[j] - s) * v;
            s = b[j];
            j += 1;
            v += 1; }}printf("%.0lf", t);
    return 0;
}
Copy the code