公交换乘
共 20 个测试点
每个测试点 5 分
每个测试点限时 1 秒
运行内存上限 256MB
查看本题最近一次测评结果
著名旅游城市 B 市为了鼓励大家采用公共交通方式出行，推出了一种地铁换乘公交车的优惠方案：
1. 在搭乘一次地铁后可以获得一张优惠票，有效期为 454545 分钟，在有效期内可以消耗这张优惠票，免费搭乘一次票价不超过地铁票价的公交车。在有效期内指开始乘公交车的时间与开始乘地铁的时间之差小于等于 454545 分钟，即 tbus−tsubway≤45t_{bus}-t_{subway} le 45tbus−tsubway≤45
2. 搭乘地铁获得的优惠票可以累积，即可以连续搭乘若干次地铁后再连续使用优惠票搭乘公交车。
3. 搭乘公交车时，如果可以使用优惠票一定会使用优惠票；如果有多张优惠票满足条件，则优先消耗获得最早的优惠票。
现在你得到了小轩最近的公共交通出行记录，你能帮他算算他的花费吗？
输入格式
输入第一行包含一个正整数 nnn，代表乘车记录的数量。
接下来的 nnn 行，每行包含 333 个整数，相邻两数之间以一个空格分隔。第 iii 行的第 111 个整数代表第 iii 条记录乘坐的交通工具，000 代表地铁，111 代表公交车；第 222 个整数代表第 iii 条记录乘车的票价 priceiprice_ipricei；第三个整数代表第 iii 条记录开始乘车的时间 tit_iti（距 000 时刻的分钟数）。
我们保证出行记录是按照开始乘车的时间顺序给出的，且不会有两次乘车记录出现在同一分钟。
输出格式
输出有一行，包含一个正整数，代表小轩出行的总花费。
数据范围
对于 303030% 的数据，n≤1000n le 1000n≤1000，ti≤106t_i le 10^6ti≤106。
另有 151515% 的数据，ti≤107t_i le 10^7ti≤107，priceiprice_ipricei 都相等。
另有 151515% 的数据，ti≤109t_i le 10^9ti≤109，priceiprice_ipricei 都相等。
对于 100100100% 的数据，n≤105n le 10^5n≤105，ti≤109t_i le 10^9ti≤109，1≤pricei≤10001 le price_i le 10001≤pricei≤1000。
【样例输入】
6
0 10 3
1 5 46
0 12 50
1 3 96
0 5 110
1 6 135
【样例输出】
36
【样例解释】
第一条记录，在第 3 分钟花费 101010 元乘坐地铁。
第二条记录，在第 46 分钟乘坐公交车，可以使用第一条记录中乘坐地铁获得的优惠票，因此没有花费。
第三条记录，在第 50 分种花费 121212 元乘坐地铁。
第四条记录，在第 96 分钟乘坐公交车，由于距离第三条记录中乘坐地铁已超过 45 分钟，所以优惠票已失效，花费 333 元乘坐公交车。
第五条记录，在第 110 分钟花费 555 元乘坐地铁。
第六条记录，在第 135 分钟乘坐公交车，由于此时手中只有第五条记录中乘坐地铁获得的优惠票有效，而本次公交车的票价为 666 元，高于第五条记录中地铁的票价 555 元， 所以不能使用优惠票，花费 666 元乘坐公交车。
总共花费 363636 元。
【样例输入2】
6
0 5 1
0 20 16
0 7 23
1 18 31
1 4 38
1 7 68
【样例输出2】
32
【样例解释2】
第一条记录，在第 1 分钟花费 555 元乘坐地铁。
第二条记录，在第 16 分钟花费 202020 元乘坐地铁。
第三条记录，在第 23 分钟花费 777 元乘坐地铁。
第四条记录，在第 31 分钟乘坐公交车，此时只有第二条记录中乘坐的地铁票价高于本次公交车票价，所以使用第二条记录中乘坐地铁获得的优惠票。
第五条记录，在第 38 分钟乘坐公交车，此时第一条和第三条记录中乘坐地铁获得的优惠票都可以使用，使用获得最早的优惠票，即第一条记录中乘坐地铁获得的优惠票。
第六条记录，在第 68 分钟乘坐公交车，使用第三条记录中乘坐地铁获得的优惠票。
总共花费 323232 元。
一开始只想到了暴力二分，后来觉得滑动窗口麻烦一点就没管…哎…
建立两个数组，price[i]和ttime[i]代表第i张优惠票所能抵消掉的最大价格和起始时间。每次坐地铁时获得优惠票，更新这两个数组，坐公交时二分查找当前时间45分钟以前的时间的位置（lower_bound），没找到的话说明这次公交只能花钱了，找到的话从那个位置向后遍历，当遇到第一张（因为要求时间优先，价格无所谓）优惠价格满足条件的优惠票时终止循环，同时给这张票打标记，说明这次能抵消了，否则不能抵消。
注意循环终止条件别少写，
共 20 个测试点
每个测试点 5 分
每个测试点限时 1 秒
运行内存上限 256MB
查看本题最近一次测评结果
著名旅游城市 B 市为了鼓励大家采用公共交通方式出行，推出了一种地铁换乘公交车的优惠方案：
1. 在搭乘一次地铁后可以获得一张优惠票，有效期为 454545 分钟，在有效期内可以消耗这张优惠票，免费搭乘一次票价不超过地铁票价的公交车。在有效期内指开始乘公交车的时间与开始乘地铁的时间之差小于等于 454545 分钟，即 tbus−tsubway≤45t_{bus}-t_{subway} le 45tbus−tsubway≤45
2. 搭乘地铁获得的优惠票可以累积，即可以连续搭乘若干次地铁后再连续使用优惠票搭乘公交车。
3. 搭乘公交车时，如果可以使用优惠票一定会使用优惠票；如果有多张优惠票满足条件，则优先消耗获得最早的优惠票。
现在你得到了小轩最近的公共交通出行记录，你能帮他算算他的花费吗？
输入格式
输入第一行包含一个正整数 nnn，代表乘车记录的数量。
接下来的 nnn 行，每行包含 333 个整数，相邻两数之间以一个空格分隔。第 iii 行的第 111 个整数代表第 iii 条记录乘坐的交通工具，000 代表地铁，111 代表公交车；第 222 个整数代表第 iii 条记录乘车的票价 priceiprice_ipricei；第三个整数代表第 iii 条记录开始乘车的时间 tit_iti（距 000 时刻的分钟数）。
我们保证出行记录是按照开始乘车的时间顺序给出的，且不会有两次乘车记录出现在同一分钟。
输出格式
输出有一行，包含一个正整数，代表小轩出行的总花费。
数据范围
对于 303030% 的数据，n≤1000n le 1000n≤1000，ti≤106t_i le 10^6ti≤106。
另有 151515% 的数据，ti≤107t_i le 10^7ti≤107，priceiprice_ipricei 都相等。
另有 151515% 的数据，ti≤109t_i le 10^9ti≤109，priceiprice_ipricei 都相等。
对于 100100100% 的数据，n≤105n le 10^5n≤105，ti≤109t_i le 10^9ti≤109，1≤pricei≤10001 le price_i le 10001≤pricei≤1000。
【样例输入】
6
0 10 3
1 5 46
0 12 50
1 3 96
0 5 110
1 6 135
【样例输出】
36
【样例解释】
第一条记录，在第 3 分钟花费 101010 元乘坐地铁。
第二条记录，在第 46 分钟乘坐公交车，可以使用第一条记录中乘坐地铁获得的优惠票，因此没有花费。
第三条记录，在第 50 分种花费 121212 元乘坐地铁。
第四条记录，在第 96 分钟乘坐公交车，由于距离第三条记录中乘坐地铁已超过 45 分钟，所以优惠票已失效，花费 333 元乘坐公交车。
第五条记录，在第 110 分钟花费 555 元乘坐地铁。
第六条记录，在第 135 分钟乘坐公交车，由于此时手中只有第五条记录中乘坐地铁获得的优惠票有效，而本次公交车的票价为 666 元，高于第五条记录中地铁的票价 555 元， 所以不能使用优惠票，花费 666 元乘坐公交车。
总共花费 363636 元。
【样例输入2】
6
0 5 1
0 20 16
0 7 23
1 18 31
1 4 38
1 7 68
【样例输出2】
32
【样例解释2】
第一条记录，在第 1 分钟花费 555 元乘坐地铁。
第二条记录，在第 16 分钟花费 202020 元乘坐地铁。
第三条记录，在第 23 分钟花费 777 元乘坐地铁。
第四条记录，在第 31 分钟乘坐公交车，此时只有第二条记录中乘坐的地铁票价高于本次公交车票价，所以使用第二条记录中乘坐地铁获得的优惠票。
第五条记录，在第 38 分钟乘坐公交车，此时第一条和第三条记录中乘坐地铁获得的优惠票都可以使用，使用获得最早的优惠票，即第一条记录中乘坐地铁获得的优惠票。
第六条记录，在第 68 分钟乘坐公交车，使用第三条记录中乘坐地铁获得的优惠票。
总共花费 323232 元。
一开始只想到了暴力二分，后来觉得滑动窗口麻烦一点就没管…哎…
建立两个数组，price[i]和ttime[i]代表第i张优惠票所能抵消掉的最大价格和起始时间。每次坐地铁时获得优惠票，更新这两个数组，坐公交时二分查找当前时间45分钟以前的时间的位置（lower_bound），没找到的话说明这次公交只能花钱了，找到的话从那个位置向后遍历，当遇到第一张（因为要求时间优先，价格无所谓）优惠价格满足条件的优惠票时终止循环，同时给这张票打标记，说明这次能抵消了，否则不能抵消。
注意循环终止条件别少写，
#include <bits/stdc++.h> using namespace std; int n, price[500005], ttime[500005]; bool flag[500005];//标记能否使用 int main() { cin >> n; int i, j, cnt = 0, op, p, t;;//cnt是优惠票总数 long long cost = 0; for(i = 1; i <= n; i++) { scanf("%d%d%d", &op, &p, &t); if(op == 0) { cnt++; price[cnt] = p; ttime[cnt] = t; flag[cnt] = 1; cost += 1ll * p; } else { int pos = lower_bound(ttime + 1, ttime + cnt + 1, t - 45) - ttime; if(pos >= 1 && pos <= cnt) { bool find = 0; for(j = pos; ttime[j] < t && j <= cnt; j++) { if(price[j] >= p && flag[j]) { flag[j] = 0; find = 1; break; } } if(!find) { cost += 1ll * p; } } else cost += 1ll * p; } } cout <<cost; }