題目背景
SOURCE：NOIP2015-SHY-5
題目描述
假設現在離 noip 還有 m 天，有 n 個人要去參加比賽。他們每個人都有一個預定的訓練量 r[i] ，是以每一天他們都抓緊時間練習。但是由于條件限制，第 i 天隻有 t[i] 的時間可以練習。
我們都知道，一個人在開始幹活以前總要浪費一些時間做一些雜七雜八的事情。現在我們假定第 i 個人每天在訓練前浪費的時間是固定的，記為 d[i] 。這段浪費掉的時間過後，選手會專心緻志訓練，他們會充分利用剩下的時間。然而一個可能的情況時，一個人還在無所事事的時候，某一天的訓練時間已經過去了，是以他那一天什麼事情都沒有做。
現在請問每個人在第幾天的時候可以完成自己的訓練任務。當然會存在志向遠大但是很懶惰的人到最後也是做不完的情況。
輸入格式
第一行兩個整數 n，m ，表示人數和天數 。
接下來一行 m 個整數 t[i] 。
接下來 n 行每行兩個整數 d[i]，r[i] 。
輸出格式
一行輸出 n 個整數表示每個人在第幾天可以完成自己的工作，如果完不成，輸出 0 。
樣例資料
輸入
3 3
4 2 5
1 3
2 5
3 4
輸出
1 3 0
備注
【資料範圍】
對 30% 的輸入資料 ：1≤n,m≤1000
對 100% 的輸入資料 ：1≤n,m≤ 200000；1≤t[i]≤1000000； 0≤d[i]≤1000000；1≤r[i]≤1000000
【注意事項】
如果某人浪費的時間超過一天，不需減去負的時間。
分析：看到這麼大的資料果斷去拿30%暴力了（然後打錯了，哇——）。很多時候看到這種最多O（n）複雜度的題都覺得無從下手呢……總結起來，好像這樣的題都離不開排序、二分：本題為先從大到小排序每天的時間和每人每天水的時間，然後開始把每個人能用功的天數逐漸加入樹狀數組，本來O（ n2 ）的枚舉複雜度成功被降為O（n）。
代碼
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<iomanip>
#include<queue>
#include<set>
using namespace std;
int getint()
{
int sum=,f=;
char ch;
for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
if(ch=='-')
{
f=-;
ch=getchar();
}
for(;isdigit(ch);ch=getchar())
sum=(sum<<)+(sum<<)+ch-;
return sum*f;
}
const int maxn=;
struct node{
int t,num,r;
}day[maxn],man[maxn];
int n,m,cnt;
long long sum[maxn];
int times[maxn],ans[maxn];
bool comp(const node &a,const node &b)
{
if(a.t==b.t)
a.num<b.num;
return a.t>b.t;
}
int lowbit(int x)
{
return x & (-x);
}
void buildtree(int num,int w)
{
for(int i=num;i<=m;i+=lowbit(i))
sum[i]+=w,times[i]+=;//記錄需要時間、水的次數
}
bool check(int x,int bh)
{
int res=;
for(int i=x;i>=;i-=lowbit(i))
res+=sum[i],res-=man[bh].t*times[i];
return res>=man[bh].r;
}
int main()
{
freopen("work.in","r",stdin);
freopen("work.out","w",stdout);
n=getint(),m=getint();
for(int i=;i<=m;++i)
{
day[i].t=getint();
day[i].num=i;//記錄每天的時間和這是第幾天
}
sort(day+,day+m+,comp);//按時間從大到小排序
for(int i=;i<=n;++i)
{
man[i].t=getint();//記錄人水的時間
man[i].r=getint();//記錄每個人的目标
man[i].num=i;//記錄這是第幾人
}
sort(man+,man+n+,comp);//按水的時間從大到小排序
cnt=;
for(int i=;i<=n;++i)
{
while(man[i].t<day[cnt].t)//隻有人沒有水完一天的時候才把這一天的時間加入樹狀數組
{
buildtree(day[cnt].num,day[cnt].t);
cnt++;
}
ans[man[i].num]=;
int l=,r=m,mid;
while(l<=r)//二分完成任務的時間，存入對應的人的答案
{
mid=(l+r)>>;
if(check(mid,i))
ans[man[i].num]=mid,r=mid-;
else
l=mid+;
}
}
for(int i=;i<=n;++i)
cout<<ans[i]<<" ";
return ;
}
本題結。
小彩蛋！本題的測試資料get！調不出來的小夥伴拿去用吧！
百度雲連結: https://pan.baidu.com/s/1hs9vcKc 密碼: z95k