小Y的炮 cannon题解

题解"/>

小Y的炮 cannon题解

题目描述

小Y最近开发出了批量制造大威力轰山炮的方法。才过去不到几个月，小Y就制造出了M门款式不同的轰山炮。第i门轰山炮发射一次，能使一座当前高度不高于Ai的山的高度降低Di（当然山的高度不能轰到0以下）。应政府要求，小Y要用他开发的轰山炮轰平开发区的几座山。由于开发区急需土地资源，政府要求小Y轰平尽量多的山（轰平：使山的高度降低至0）。

但是小Y制造的弹药有限，导致他最多只能发射K次。

小Y想知道，他最多能轰平几座山？轰平这些山后，弹药最多还够他发射几次？

输入

第一行三个正整数N,M,K，分别表示山的数目、轰山炮的款式数目、最多发射次数。
接下来N行，每行一个正整数Hi，表示第i座山的高度，输入数据保证Hi是降序的（从大到小）。
接下来M行，每行两个正整数Ai,Di，分别表示第i款轰山炮能轰的山的最高高度，和轰掉的山高度的减少值。

输出

一行两个整数Max,Remain,分别表示最多轰平的山的数目和轰平这些山后最多的剩余发射次数。

样例输入

3 2 3
8
6
2
10 6
6 5

样例输出

2 1

提示

【样例解释】

将高度为6和高度为2的山轰平，使用第一款轰山炮，各只需1次即可轰平。高度为8的山最少需要2次，弹药不够用。所以最多轰平2座山，剩余1次发射次数。

【数据范围】

20%的数据满足N<=100,M<=100,Hi,Ai<=100。50%的数据满足N<=1000,M<=500。80%的数据满足N<=250000,M<=500。20%、50%、80%的数据均满足Hi,Ai<=1000000。100%的数据满足N<=250000,M<=500,K,Hi,Ai<=10^18,Di<=500。

【时限】

测试时限为0.5s

附上标准题解

显然，轰平高度低的山的次数总是不多于轰平高度高的山的次数，所以优先轰高度低的山总是最优的。

20%：从低到高枚举每一座可以被轰的山。对于每座山，不同高度时可以选用的大炮是不同的。那么对于当前高度H，选出Di最大的可以用的大炮，把山的高度H降至H-Di，接着再类似做，直到H被降至0或0以下。总效率O(NMH)。

考虑所有的大炮，假如存在大炮i,j满足：Ai>=Aj,Di>=Dj，那么在任何情况下，大炮i都是比大炮j要优的。大炮j是没用的。

舍去所有没用的大炮后{你可以用排序+单调队列做(O(MlogM))，也可以排序+枚举判定是否舍弃(O(M^2))}，我们得到了剩下有用的大炮。这些大炮总是Ai递增，Di递减的。

   这样，剩下的S门大炮就将高度分成了S个区间。每个区间的Di是固定的，即假如高度H处于第i个区间中，那么发射一次最多降至H-Di。

50%：从低到高枚举每一座可以被轰的山。对于每座山，求出当前高度H所在区间i，求出下一个区间的最高高度A[i-1]，将H降至H-t*Di，满足H-t*Di刚好<=A[i-1] (即H-(t-1)*Di>A[i-1]且H-t*Di<=A[i-1])，接着再类似做，直到H被降至0或0以下。寻找所在区间i可以使用二分查找(O(logM))，不过由于高度递减，所以通过线性扫描可以做到平摊(O(1))。

总效率O(NMlogM)或O(NM)。

80%：由于H的范围很小，所以可以先预处理出轰平所有高度的山所需要的最少发射次数F[H]。从小到大枚举H，求出其所在区间i，那么有递推关系F[H]=F[H-Di]+1。寻找所在区间i可以使用二分，由于高度递增，线性扫描也可以。

之后对于每座可以被轰的山，都可以用O(1)的时间得到轰平所需的最少发射次数。

总效率O(N+MlogM+H)。

100%：注意到D的范围很小。假如一个高度H在区间i内，一直降低，在H刚好降低到刚好比A[i-1]小时，总有A[i-1]-H<=D。对于任何高度都有上述结论。所以我们最多只需处理O(M*D)个高度即可。令F[H]为轰平H高度的山的最少发射次数，则对于某个高度H，一直降至H-t*Di<=A[i-1]，有F[H]=F[H-t*Di]+t，由于有用的H最多只有O(M*D)个，所以这样做的效率为O(M*D)。（F数组可由HASH代替）

那么对于从低到高的每座山，设该山高度为H，找到H对应的区间i(O(N+M))，将H降至H-t*Di<=A[i-1]，那么最少发射次数为t+F[H-t*Di]，其中H-t*Di必然是O(M*D)个高度中的一个。所以对于每座可以被轰的山，都可以用O(1)的时间得到轰平所需的最少发射次数。

总效率O(N+MlogM+MD)。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <map>
#define MAXN 250005
using namespace std;
typedef long long ll;
int n,m,cnt;
bool flag[505];
ll k,low,ans,t,h[MAXN];
map <ll,ll> f;
struct Node
{ll a,d;
}p[505],q[505];
inline bool cmp(Node x,Node y)
{return x.a<y.a||x.a==y.a&&x.d<y.d;
}
int main()
{scanf("%d%d%lld",&n,&m,&k);for (int i=n;i>=1;i--)scanf("%lld",&h[i]);for (int i=1;i<=m;i++)scanf("%lld%lld",&p[i].a,&p[i].d);sort(p+1,p+1+m,cmp);for (int i=1;i<=m;i++){while(cnt>0&&q[cnt].d<=p[i].d)cnt--;q[++cnt]=p[i];}f[0]=0;for (int i=1;i<=cnt;i++){if(i!=1)low=q[i-1].a;ll st=max(low,q[i].a-q[i].d)+1,ed=q[i].a;for (ll h=st;h<=ed;h++){t=(h-low-1)/q[i].d+1;f[h]=f[max(0ll,h-t*q[i].d)]+t;}}int j=1;low=0;for (int i=1;i<=n;i++){while(q[j].a<h[i]&&j<=cnt)j++;if(j>cnt)break;if(j!=1)low=q[j-1].a;t=(h[i]-low-1)/q[j].d+1;ll tot=f[max(0ll,h[i]-t*q[j].d)]+t;if(tot<=k)k-=tot,ans++;else break;}cout<<ans<<" "<<k<<endl;return 0;
}