3441: 乌鸦喝水
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 374 Solved: 148
[Submit][Status][Discuss]Description
【题目背景】一只乌鸦在自娱自乐，它在面前放了n个有魔力的水缸，水缸里装有无限的水。【题目描述】他准备从第1个水缸飞到第n个水缸，共m次。在飞过一个水缸的过程中，如果他能够得着水缸里的水，即水缸口到水面距离 小于等于乌鸦能够得着的深度，那它就会喝水缸里的水。每喝一次水， 所有水缸里的水位都会下降，第i个水缸里的水位会下降Ai，注意喝水是瞬间的，如果乌鸦刚好够得着，但喝完之后够不着，也视为喝到一次，水位也会相应的下降。Input
共有3行。第一行有三个正整数n、m和x，用空格隔开。n表示水缸的数量，m表示乌鸦飞的次数，x表示乌鸦能够得着的深度。第二行，有n个用空格隔开的正整数，第i个数为第i个水缸中水缸口到水面的距离Wi。第三行，有n个用空格隔开的正整数，第i个为Ai。Output
只有一行，这一行只有一个正整数，为这只乌鸦能喝到水的次数。Sample Input
5 2 20
15 14 13 12 12
1 1 1 1 1
Sample Output
9
【数据范围】
100%的数据，0＜n≤100000，0＜m≤100000，0＜x≤2000000000，0＜Wi≤2000000000，0＜Ai≤200。
HINT
2016.7.8重设时限，未重测！
Source
By lll6924 at “酱油杯noi考后欢乐赛”
题解
首先计算出每个水缸里的水能喝几次, 然后推出一个结论: 水少的水缸如果喝了 $n$ 次, 则水比它多的水缸也至少喝了 $n$ 次.
继续推还可以推出: 如果某一轮从某个水缸一直到结尾还能喝 $k$ 次, 而且该还能喝的次数 $\geq k$ , 则水比该水缸多的水缸不会在本轮被喝完.
然后我们就可以把水缸按照还可以喝的次数升序排序, 树状数组维护查询某水缸到结尾还能喝几次, 贪心处理即可
参考代码
GitHub
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <iostream> 5 #include <algorithm> 6 7 const int MAXN=1e6+10; 8 9 int n; 10 int m; 11 int x; 12 int r; 13 int ans; 14 int cnt; 15 int last; 16 int c[MAXN]; 17 18 std::pair<int,int> a[MAXN]; 19 20 int Query(int); 21 int LowBit(int); 22 void Add(int,int); 23 void Initialize(); 24 int BinarySearch(int); 25 26 int main(){ 27 Initialize(); 28 for(int i=1;i<=cnt;i++){ 29 if(a[i].first<ans){ 30 Add(a[i].second,-1); 31 } 32 else{ 33 int tmp=Query(cnt)-Query(last); 34 while(r<m&&ans+tmp<=a[i].first){ 35 r++; 36 ans+=tmp; 37 last=0; 38 tmp=Query(cnt)-Query(last); 39 } 40 if(r>=m) 41 break; 42 int pos=BinarySearch(a[i].first-ans); 43 ans=a[i].first; 44 last=pos; 45 Add(a[i].second,-1); 46 } 47 } 48 printf("%d\n",ans); 49 return 0; 50 } 51 52 int BinarySearch(int x){ 53 int ans=last,l=last,r=cnt; 54 while(l<=r){ 55 int mid=(l+r)>>1; 56 if(Query(mid)-Query(last)<=x){ 57 ans=mid; 58 l=mid+1; 59 } 60 else 61 r=mid-1; 62 } 63 return ans; 64 } 65 66 void Initialize(){ 67 int tmp; 68 scanf("%d%d%d",&n,&m,&x); 69 for(int i=1;i<=n;i++){ 70 scanf("%d",&a[i].first); 71 a[i].second=i; 72 } 73 for(int i=1;i<=n;i++){ 74 scanf("%d",&tmp); 75 a[i].first=(x-a[i].first)/tmp+1; 76 } 77 for(int i=1;i<=n;i++){ 78 if(a[i].first!=0){ 79 a[++cnt]=a[i]; 80 Add(a[i].second,1); 81 } 82 } 83 std::sort(a+1,a+1+cnt); 84 } 85 86 void Add(int i,int x){ 87 while(i<=n){ 88 c[i]+=x; 89 i+=LowBit(i); 90 } 91 } 92 93 int Query(int x){ 94 int ans=0; 95 while(x>0){ 96 ans+=c[x]; 97 x-=LowBit(x); 98 } 99 return ans; 100 } 101 102 inline int LowBit(int x){ 103 return x&-x; 104 }
