CSP-J T2 O(N^2)进行优化成功AC
  • 板块灌水区
  • 楼主yuhao7370
  • 当前回复15
  • 已保存回复15
  • 发布时间2019/11/17 14:07
  • 上次更新2024/8/13 19:32:54
查看原帖
CSP-J T2 O(N^2)进行优化成功AC
154581
yuhao7370楼主2019/11/17 14:07
#include<bits/stdc++.h>
using namespace std;
struct node {
	int time,price,used;
};
node ticket[100005];
int cnt=1,ans=0,n;
int tran,cost,t,start=1;
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; ++i) {
		scanf("%d%d%d",&tran,&cost,&t);
		if(tran==0) {
			ticket[cnt].price=cost;
			ticket[cnt].time=t;
			ticket[cnt].used=0;
			++cnt;
			ans+=cost;
		} else {
			for(int j=start; j<cnt; ++j) {
				if(t-ticket[j].time>45)
					start=j;
				else {
					if(ticket[j].price>=cost&&!ticket[j].used) {
						cost=0,ticket[j].used=1;
						break;
					}
				}
			}
			ans+=cost;
		}
	}
	printf("%d",ans);
	return 0;
}
2019/11/17 14:07
加载中...