首页 > 代码库 > 【差分+二分】借教室

【差分+二分】借教室

2024-11-04 04:52:38   206人阅读

因为是按订单顺序处理的，所以前面的订单都能处理，后面的订单都不能处理，所以可以通过二分得到第一个不能满足的订单

这里和之前的二分不太一样，注意，如果所有的订单都能满足的话ans将不会被赋值，所以需要提前设置ans的值

int l=1,r=m,mid,ans=m;

 while(l<=r)
 {
  mid=(l+r)/2;
  if (check(mid))
   l=mid+1;
  else
  {
   ans=mid;
   r=mid-1;
  }
 }

给出了订单的开始时间和结束时间，所以很容易想到用差分

所谓差分就是将一个对区间的操作变为对区间端点的操作

sum[s[i]]+=d[i];

sum[t[i]+1]-=d[i];

 1 #include <cstdio>
 2 #include <cstring>
 3 int n,m,r[1000001],d[1000001],s[1000001],t[1000001],sum[1000001];
 4 inline int read(int &x)
 5 {
 6     char ch=getchar();x=0;
 7     for (;ch<‘0‘||ch>‘9‘;ch=getchar());
 8     for (;ch>=‘0‘&&ch<=‘9‘;ch=getchar())x=x*10+ch-‘0‘;
 9 }
10 inline bool check(int x)
11 {
12     memset(sum,0,sizeof(sum));
13     int dsum=0;
14     for (int i=1;i<=x;i++)
15     {
16         sum[s[i]]+=d[i];
17         sum[t[i]+1]-=d[i];
18     }
19     for (int i=1;i<=n;i++)
20     {
21         dsum+=sum[i];
22         if (dsum>r[i]) return 0;
23     }
24     return 1;
25 }
26 int main()
27 {
28     read(n);read(m);
29     for (int i=1;i<=n;i++) read(r[i]);
30     for (int i=1;i<=m;i++) read(d[i]),read(s[i]),read(t[i]);
31     int l=1,r=m,mid,ans=m;
32     while(l<=r)
33     {
34         mid=(l+r)/2;
35         if (check(mid))
36             l=mid+1;
37         else
38         {
39             ans=mid;
40             r=mid-1;
41         }
42     }
43     if (ans==m)
44         printf("0");
45     else
46         printf("-1\n%d",ans);
47 }

 

【差分+二分】借教室


联系
我们