贝茜放慢脚步(寒假每日一题 14)

奶牛贝茜正在参加冬季哞林匹克运动会的越野滑雪比赛。

她以每秒 1 米的速度出发。

但是,随着时间的推移,她变得越来越疲倦,她开始放慢脚步。

每次放慢脚步,贝茜的速度都会降低:减速一次后,她以每秒 1/2 米的速度移动,减速两次后,则以每秒 1/3 米的速度移动,依此类推。

你将被告知何时何地贝茜会减速。

当减速信息格式为:

T 17
意味着,贝茜在某个时间点减速,本例表示比赛开始第 17 秒贝茜减速。

当减速信息格式为:

D 10
意味着,贝茜在某个地点减速,本例表示在行进 10 米处减速。

给定 N 个减速信息,请计算贝茜滑完一千米需要多少秒。

将你的答案四舍五入到最接近的整数( 0.5 向上舍入为 1)。

输入格式
第一行包含整数 N N N。

接下来 N N N 行,每行描述一个减速信息,格式为 T xD x

无论哪种情况,x 都是一个整数,保证所有减速都在贝茜滑完一千米前发生。

可能同时发生多次减速,那么这会使得贝茜的速度一下子变慢很多。

所有减速信息不一定按顺序给出。

输出格式
输出贝茜滑完一千米所需的总时间。

数据范围
1 ≤ N ≤ 10000 1≤N≤10000 1≤N≤10000

输入样例:

2
T 30
D 10

输出样例:

2970

样例解释
贝茜以每秒 1 米的速度跑完前 10 米,耗时 10 秒。

然后她减速到每秒 1 / 2 1/2 1/2 米,接下来的 10 米要花 20 秒。

然后她在第 30 秒时,再次减速到每秒 1/3 米。

滑完剩下的 980 米需要 980 × 3 = 2940 980×3=2940 980×3=2940 秒。

因此,总时间是 10 + 20 + 2940 = 2970 10+20+2940=2970 10+20+2940=2970 秒。


两路归并

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 10010;


int n;
vector<int> a, b;

int main(){
    
    scanf("%d", &n);
    
    char str[2];
    int x;
    while(n--){
        
        scanf("%s%d", str, &x);
        if(*str == '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 t = 0, s = 0, v = 1;  // v是倒数
    int i = 0, j = 0;
    while(i < a.size() && j < b.size()){
        
        if(a[i] - t < (b[j] - s) * v){
            
            s += (a[i] - t) / v;
            t = a[i];
            v++;
            i++;
        }else{
            
            t += (b[j] - s) * v;
            s = b[j];
            v++;
            j++;
        }
    }
    
    while(i < a.size()){
        s += (a[i] - t) / v;
        t = a[i];
        v++;
        i++;
    }
    
    while(j < b.size()){
        t += (b[j] - s) * v;
        s = b[j];
        v++;
        j++;
    }
    
    printf("%.0lf\n", t);
    
    return 0;
}
上一篇:汇编代码题


下一篇:基于区域增长(RegionGrowing)的分割算法——参照pcl源码