首页 > 代码库 > tyvj P4751 NOIP春季系列课程 H's Problem
tyvj P4751 NOIP春季系列课程 H's Problem
-H‘s Problem-
描述
小H是一个喜欢逛街的女孩子，但是由于上了大学，DDL越来越多了，她不能一直都处于逛街的状态。为了让自己能够更加沉迷于学习，她规定一次逛街只逛T个单位的时间。
小H从1号店出发，从1号店走到第i号店需要花费ai的时间，这些店形成了一条直线，也就是说小H从第i号店走到第i+1号店需要花费的时间为a{i+1}-ai。若小H选择了第i号店并且进去逛，则会消耗bi的时间。对于第i家店，小H都对它有自己的看法。具体地，可以用ci来表示小H是否喜欢这家店。如果ci=1，则表示小H喜欢i号店，否则若ci=0，则表示小H不喜欢这家店。
小H想尽可能逛更多的店，但是她也有属于自己的目标，也就是说逛至少k家喜欢的店，在这个基础上，能逛的店越多越好。
小H现在想知道自己最多能逛多少店，当然若小H无论如何也逛不到k家喜欢的店，那么你输出-1就行了。
输入格式
第一行3个数n,T,k。
接下来一行n个数表示ai。
接下来一行n个数表示bi。
接下来一行n个数表示ci。
输出格式
输出一个数表示答案。
输入样例
4 11 1
0 1 2 10
1 1 1 1
0 0 0 1
输出样例
1
数据范围
对于20%的数据n<=20。
对于40%的数据n<=1000。
对于100%的数据n<=100000，1<=T<=10^9，0<=k<=n，a1=0，a1<a2<…<an<=10^9，1<=bi<=10^9，0<=ci<=1，数据有梯度。
一道蛮有趣的数据结构题；
先分析下题意，我们要求的是在 1~n 中选择尽量多的店去逛，同时至少逛k家我们喜欢的店；
因为到每家店所需时间不同，我们走的越远，剩余逛店时间就越少，但可选择的店会增多，所以答案上不具备单调性，只能枚举每一个点作为终点，然后分别求答案数；
对于任意一点 i 作为终点求答案数，实际就是在 1~i 中选择尽量多的点，即求一个动态升序数组的前 x 项，使它们的和 <= T-a[i]；
我们注意到元素的插入顺序和元素大小都是已知的，因此可以通过离散化 + 排序，预处理出所有元素在数组中应在的位置，然后构建一个静态数组，将元素按顺序放进它应在的位置，这样较动态维护快出很多；
因为数组中元素有序，所以我们求前缀和即可；
对一个动态数组进行单点修改和求前缀和，很明显可以使用树状数组（当然线段树也可）；
树状数组中下标代表元素大小（离散化后），每个节点存储元素个数及元素权值和（离散化前）；
前缀和是连续的，因此可以对下标进行二分查找；
最后对于必须逛够 k 家喜欢的店的问题，因为只需选择 1~i 中前 k 家耗时最少的店，我们可以维护一个大根堆，存储前 k 小的 k 个元素，从堆中踢出或未进堆元素则存入树状数组；
复杂度方面，枚举终点 O（n），排序 + 离散化 O（n*logn），二分 + 树状数组查询（修改） O（logn*logn），堆维护 O（logn），总复杂度 O（n*logn*logn）；
（实际上还可以用平衡树做，复杂度貌似可以降至 O（n*logn）
AC GET☆DAZE（大概
↓代码（只有70分，希望dalao们能帮我挑挑错（堆写的很恶心orz
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<vector> 7 #define ll long long 8 #define MAX_L 0x7fffffff7fffffff 9 using namespace std; 10 struct mk 11 { 12 ll c,r; 13 }; 14 struct poi 15 { 16 ll n,s; 17 }; 18 mk shop[100039]; 19 poi tree[100039]={0}; 20 ll rou[100039],tim[100039],ord[100039],hea[100039]={0},size=0,n,sum,calcs; 21 bool kn[100039]={0}; 22 bool cmp(mk a,mk b) 23 { 24 return a.c<b.c; 25 } 26 void ueni() 27 { 28 ll a=size,key=hea[size]; 29 while(1) 30 { 31 if(tim[hea[a/2]]<tim[key]) 32 { 33 hea[a]=hea[a/2]; 34 a/=2; 35 } 36 else 37 { 38 hea[a]=key; 39 return; 40 } 41 } 42 } 43 void sitani() 44 { 45 ll a=1,key=hea[1],ne; 46 while(1) 47 { 48 ne=a*2; 49 if(tim[hea[a*2]]<tim[hea[a*2+1]]) 50 { 51 ne++; 52 } 53 if(a*2>size) 54 { 55 hea[a]=key; 56 return; 57 } 58 if(tim[hea[ne]]>tim[key]) 59 { 60 hea[a]=hea[ne]; 61 a=ne; 62 } 63 else 64 { 65 hea[a]=key; 66 return; 67 } 68 } 69 } 70 ll lowbit(ll k) 71 { 72 return -k&k; 73 } 74 void maketree(ll x) 75 { 76 ll a=ord[x]; 77 while(a<=n) 78 { 79 tree[a].n+=tim[x]; 80 tree[a].s++; 81 a+=lowbit(a); 82 } 83 return; 84 } 85 ll calctree(ll x) 86 { 87 ll calcn=0,a=x; 88 calcs=0; 89 while(a) 90 { 91 calcn+=tree[a].n; 92 calcs+=tree[a].s; 93 a-=lowbit(a); 94 } 95 return calcn; 96 } 97 int main() 98 { 99 mk stp;100 ll T,k,t,l,r,m,ans=-1,a,b,c;101 scanf("%lld%lld%lld",&n,&T,&k);102 for(a=1;a<=n;a++)103 {104 scanf("%lld",&rou[a]);105 }106 for(a=1;a<=n;a++)107 {108 scanf("%lld",&tim[a]);109 stp.c=tim[a];110 stp.r=a;111 shop[a]=stp;112 }113 for(a=1;a<=n;a++)114 {115 scanf("%lld",&kn[a]);116 }117 sort(shop+1,shop+n+1,cmp);118 for(a=1;a<=n;a++)119 {120 ord[shop[a].r]=a;121 }122 tim[0]=MAX_L;123 for(a=1;a<=n;a++)124 {125 if(kn[a])126 {127 if(size<k)128 {129 T-=tim[a];130 hea[++size]=a;131 ueni();132 }133 else134 {135 if(hea[1]!=0 && tim[a]<tim[hea[1]])136 {137 T-=tim[a];138 T+=tim[hea[1]];139 maketree(hea[1]);140 hea[1]=a;141 sitani();142 }143 else144 {145 maketree(a);146 }147 }148 }149 else150 {151 maketree(a);152 }153 t=T-rou[a];154 if(size==k && t>=0)155 {156 l=1,r=n;157 while(l+39<r)158 {159 m=(l+r)>>1;160 if(calctree(m)<=t)161 {162 l=m;163 }164 else165 {166 r=m;167 }168 }169 while(calctree(l)<=t && l<=n)170 {171 l++;172 sum=calcs;173 }174 ans=max(ans,sum+k);175 }176 }177 printf("%lld",ans);178 return 0;179 }
tyvj P4751 NOIP春季系列课程 H's Problem