首页 > 代码库 > URAL 2014 Zhenya moves from parents --线段树
URAL 2014 Zhenya moves from parents --线段树
题意：儿子身无分文出去玩，只带了一张他爸的信用卡，当他自己现金不足的时候就会用信用卡支付，然后儿子还会挣钱，挣到的钱都是现金，也就是说他如果有现金就会先花现金，但是有了现金他不会还信用卡的钱。他每花一次钱和挣一次钱都会给他爸发一条短信，告诉他挣/花的钱和时间，但是给出的短信顺序时间可能不是按顺序来的，然后他爸要根据现有的短信信息推测信用卡现在的负债是多少。
解法： 因为挣的钱或花的钱都只影响后面时间的负债，时间离散，每加入一个值，都更新这个pos到n的所有值，然后整个时间最小的值就是答案。结果与0取个最小值就可以了。但是一直不太了解这个原理，求大神解释。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#define lll __int64using namespace std;#define N 100017lll Min[4*N],mark[4*N],b[N];struct node{ lll val,tim;}a[N];void pushup(int rt) { Min[rt] = min(Min[rt<<1],Min[rt<<1|1]); }void pushdown(int l,int r,int rt){ if(mark[rt]) { mark[rt<<1] += mark[rt]; mark[rt<<1|1] += mark[rt]; Min[rt<<1] += mark[rt]; Min[rt<<1|1] += mark[rt]; mark[rt] = 0; }}void build(int l,int r,int rt){ Min[rt] = mark[rt] = 0; if(l == r) return; int mid = (l+r)/2; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); pushup(rt);}void update(int l,int r,int aa,int bb,lll val,int rt){ if(aa <= l && bb >= r) { Min[rt] += val; mark[rt] += val; return; } pushdown(l,r,rt); int mid = (l+r)/2; if(aa <= mid) update(l,mid,aa,bb,val,rt<<1); if(bb > mid) update(mid+1,r,aa,bb,val,rt<<1|1); pushup(rt);}lll GetTime(){ int date,month,hour,minu; scanf("%d.%d %d:%d",&date,&month,&hour,&minu); return (lll)month*31LL*24*60 + date*24LL*60 + 60LL*hour + minu;}int main(){ int n,i,j; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%I64d",&a[i].val); a[i].tim = GetTime(); b[i] = a[i].tim; } sort(b+1,b+n+1); build(1,n+10,1); for(i=1;i<=n;i++) { lll pos = lower_bound(b+1,b+n+1,a[i].tim)-b; update(1,n+10,pos,n,a[i].val,1); printf("%I64d\n",min(0LL,Min[1])); } return 0;}
URAL 2014 Zhenya moves from parents --线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。