bzoj：3441 乌鸦喝水
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。
Solution
每一口井下降的次数是固定，wat[i]=(x-W[i])/A[i]+1;
只考虑次数就行了，每次减Ai挺麻烦的。
先把井（筛掉一开始就喝不了的井，也就是次数为0的井）按次数从小到大排序（相同的序号大的排在前面）。
一个简单的推论：i＜j，那么井i一定比井j先消失。
假设前面一共喝了tu轮。
对于第i口井，可以知道还剩s口井，二分出一个答案cnt，表示第i口井除了前面喝的还可以被喝的次数。
（scnt＜wat[i]-last中cnt所能取的最大值，last表示之前的每一口井喝的总次数。水位是一起下降的）
第i口井还可以喝cnt轮，那么后面的井也一定还可以喝cnt轮。
num[i]=tu+cnt （表示第i口井被喝的次数）
再判断序号小于id[i]且仍存在的井的个数（用树状数组），是否可以让第i口井再喝一次（也就是剩余的次数是否大于 在该井之前包括该井的井数，能则last++,num[i]++）。
last+=scnt 把喝了的井的次数加上。
tu+=cnt
s-=1 剩余的井数减一。
把每口井喝的次数num[i]加起来就是答案。
时间复杂度O(N logN)
图大概是这样的（井是经过排序的）
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
3 4 5 6 7 8 9
……
CODE
#include<cstdio>
#include<algorithm>
#define imax(a,b) ((a>b)?(a):(b))
typedef long long ll;
using namespace std;
typedef long long ll;
const int N=120000;
int n,m,tu,wat[N],wo;
ll ans,T[N],num[N],q[N],d[N],s,last,x;
bool cmp(int A,int B) {
return (q[A]<q[B] || (q[A]==q[B] && B>A));
}
void add(int x) { for(int i=x;i<=n+1;i+=(i&-i)) T[i]++; }
ll query(int x) { ll G=0; for(int i=x;i;i-=(i&-i)) G+=T[i]; return G; }
ll find(ll X,ll Y)
{
ll L=0,R=m-tu;
while(L+1<R)
{
ll Mid=(L+R)>>1;
if(Mid*Y<=X) L=Mid; else R=Mid;
}
if(R*Y<=X) L=R;
return L;
}
int main()
{
freopen("2238.in","r",stdin);
freopen("2238.out","w",stdout);
scanf("%d%d%lld",&n,&m,&x); wo=0;
for(int i=1;i<=n;i++) scanf("%lld",&d[i]);
for(int i=1;i<=n;i++)
{
ll B; scanf("%lld",&B);
ll C=imax(0ll,(x-d[i])/B+1);
if(C>0) q[++wo]=C,wat[wo]=wo;
}
sort(wat+1,wat+1+wo,cmp);
s=wo; last=0; tu=0; ans=0;
for(int i=1;i<=wo;i++)
{
ll cnt=find(q[wat[i]]-last,s);
if(cnt+tu==m)
{
ans+=(wo-i+1)*m;
printf("%lld\n",ans);
return 0;
}
if(q[wat[i]]-last-s*cnt-wat[i]+query(wat[i])>=0)
{
num[wat[i]]=cnt+tu+1;
last++;
} else num[wat[i]]=cnt+tu;
last+=s*cnt; s--; tu+=cnt;
add(wat[i]); ans+=num[wat[i]];
}
printf("%lld\n",ans);
return 0;
}