说一下几种做法:
- y总的单调队列做法,45m可以看成滑动窗口,用单调队列维护。
- 枚举地铁,尝试优惠公交
- 枚举公交,尝试使用地铁优惠
我选择的是枚举地铁,时间判断。
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
struct Node
{
int c, price, t;
}alls[N];
int main()
{
long long int sum = 0;
cin >> n;
for(int i = 0; i < n; i ++)
{
int op, op2, op3;
scanf("%d%d%d", &op, &op2, &op3);
alls[i].c = op, alls[i].price = op2, alls[i].t = op3;
if(alls[i].c == 0) sum += alls[i].price;
}
for(int i = 0; i < n; i ++)
if(alls[i].c == 0)
for(int j = i + 1; j < n; j ++)
{
if(alls[j].t - alls[i].t <= 45 && alls[i].price >= alls[j].price && alls[j].c == 1 && alls[j].price != 0)
{
alls[i].price = 0, alls[j].price = 0;
break;
}
if(alls[j].t - alls[i].t > 45) break;
}
for(int i = 0; i < n; i ++)
if(alls[i].c == 1)
sum += alls[i].price;
printf("%lld", sum);
}
顺手给一个调试器:
/*
if( i == 2 && j == 3)
{
cout << alls[i].c << ' ' << alls[i].price << ' ' << alls[i].t << ' ' << alls[j].c << ' ' << alls[j].price << ' ' << alls[j].t << endl;
if(alls[j].t - alls[i].t <= 45) cout << "1Yes ";
if(alls[i].price >= alls[j].price) cout << "2Yes ";
if(alls[j].c == 1) cout << "3Yes ";
if(alls[j].price != 0) cout << "4Yes ";
cout << endl;
}
*/
update: 单调队列解法AC代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
const int N = 100010;
int n;
struct Node
{
int c, price, t;
}alls[N];
pair<int, int> q[N];
int hh = 0, tt = -1;
bool st[N];
int main()
{
cin >> n;
for(int i = 0; i < n; i ++)
{
cin >> alls[i].c >> alls[i].price >> alls[i].t;
}
long long int res = 0;
for(int i = 0; i < n; i ++)
{
if(alls[i].c == 0)
{
res += alls[i].price;
q[ ++ tt ] = {alls[i].price, alls[i].t};
}
else
{
bool flag = false;
while(hh <= tt && alls[i].t - q[hh].second > 45) hh ++;
for(int j = hh; j <= tt; j ++)
if(q[j].first >= alls[i].price && st[j] == false)
{
st[j] = true;
flag = true;
break;
}
if(flag == false) res += alls[i].price;
}
}
cout << res << endl;
return 0;
}