刷题总结——work（ssoj）

题目:

题目背景

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 。

样例数据 1

输入　 [复制]

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

【注意事项】
如果某人浪费的时间超过一天，不需减去负的时间

题解：

本来想用二分套主席树写的·····

然而tmT了一下午弃疗了···

正解应该是将每天的训练时间按T为关键字降序排序···将每个人按其耽误时间d为关键字降序排序·····这样做是为了消除当人的浪费时间超过某一天时带来的影响·····

然后按照排好的序开始枚举对应的人···将T大于这个人r的训练天数加入两个树状数组··一个储存总时间一个储存总天数·····然后对这个人二分答案即可···

代码：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<cctype>

#include<cstring>

#include<algorithm>

#include<string>

using namespace std;

const int N=2e5+;

struct node1

{

  int day,t;

}train[N];

struct node2

{

  int person,d,r;

}peo[N];

int n,m,ans[N];

inline int R()

{

  char c;int f=;

  for(c=getchar();c<''||c>'';c=getchar());

  for(;c<=''&&c>='';c=getchar())

    f=(f<<)+(f<<)+c-'';

  return f;

}

inline bool cmp1(node1 a,node1 b)

{

  return a.t>b.t;

}

long long trsum[N],trcnt[N];

inline bool cmp2(node2 a,node2 b)

{

  return a.d>b.d;

}

inline void insertsum(int pos,int v)

{

  for(int i=pos;i<=m;i+=(i&(-i)))

    trsum[i]+=v;

}

inline void insertcnt(int pos)

{

  for(int i=pos;i<=m;i+=(i&(-i)))

    trcnt[i]++;

}

inline long long querysum(int pos)

{

  long long ans=;

  for(int i=pos;i;i-=(i&(-i)))

    ans+=trsum[i];

  return ans;

}

inline int querycnt(int pos)

{

  int ans=;

  for(int i=pos;i;i-=(i&(-i)))

    ans+=trcnt[i];

  return ans;

}

inline bool check(int x,int now)

{

  long long sum=querysum(x);

  int cnt=querycnt(x);

  if(sum-cnt*peo[now].d>=peo[now].r)  return true;

  else return false;

}

int main()

{

  //freopen("a.in","r",stdin);

  n=R(),m=R();

  for(int i=;i<=m;i++)  train[i].day=i,train[i].t=R();

  sort(train+,train+m+,cmp1);

  for(int i=;i<=n;i++)  peo[i].person=i,peo[i].d=R(),peo[i].r=R();

  sort(peo+,peo+n+,cmp2);

  int tail=;

  for(int i=;i<=n;i++)

  {

    while(train[tail].t>=peo[i].d&&tail<=m)

    {

      insertsum(train[tail].day,train[tail].t);

      insertcnt(train[tail].day);

      tail++;

    }

    int le=,ri=m,anss=;

    while(le<=ri)

    {

      int mid=(le+ri)/;

      if(check(mid,i)) ri=mid-,anss=mid;

      else le=mid+;

    }

    ans[peo[i].person]=anss;

  }

  for(int i=;i<=n;i++)  cout<<ans[i]<<" ";

  return ;

}

巴特西