题解

51 条题解

  • 0
    @ 2015-09-03 17:46:21

    #include <iostream>
    #include <stdio.h>

    using namespace std;

    int value[4 * 1000000];
    int tag[4 * 1000000];
    int a[1000000 + 2];

    inline int min( int a , int b )
    {
    if( a > b )
    return b;
    return a;
    }

    inline void pushdown( int n , int l , int r )
    {
    if( l == r )
    value[n] += tag[n];
    else
    {
    tag[ n << 1 ] += tag[n];
    tag[ ( n << 1 ) + 1 ] += tag[n];
    value[n] = min( value[ n << 1 ] + tag[ n << 1 ] , value[ ( n << 1 ) + 1 ] + tag[ ( n << 1 ) + 1 ] );
    }
    tag[n] = 0;
    return;
    }

    int build( int n , int l , int r )
    {
    if( l == r )
    return value[n] = a[l];
    return value[n] = min( build( n << 1 , l , ( l + r ) >> 1 ) , build( ( n << 1 ) + 1 , ( ( l + r ) >> 1 ) + 1 , r ) );
    }

    int find( int n , int l , int r , int a , int b , int v )
    {
    pushdown( n , l , r );
    if( l == a && r == b )
    {
    tag[n] -= v;
    pushdown( n , l , r );
    return value[n];
    }
    int mid = ( l + r ) >> 1;
    if( a > mid )
    {
    int ans = find( ( n << 1 ) + 1 , mid + 1 , r , a , b , v );
    pushdown( n , l , r );
    return ans;
    }
    else if( mid >= b )
    {
    int ans = find( n << 1 , l , mid , a , b , v );
    pushdown( n , l , r );
    return ans;
    }
    int ans = min( find( n << 1 , l , mid , a , mid , v ) , find( ( n << 1 ) + 1 , mid + 1 , r , mid + 1 , b , v ) );
    pushdown( n , l , r );
    return ans;
    }

    int n , m;
    int l , r , v;
    int i;

    int main()
    {
    scanf( "%d %d" , &n , &m );
    for( i = 1 ; i <= n ; i++ )
    scanf( "%d" , &a[i] );
    build( 1 , 1 , n );
    for( i = 1 ; i <= m ; i++ )
    {
    scanf( "%d %d %d" , &v , &l , &r );
    if( find( 1 , 1 , n , l , r , v ) < 0 )
    {
    printf( "-1\n%d\n" , i );
    return 0;
    }
    }
    printf( "0\n" );
    return 0;
    }
    95分。。。。。。

  • 0
    @ 2015-07-28 09:41:56

    这题暴力加和都可以得40分,但要都过得二分订单+前缀和+优化判定单才能AC
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    int n,m,l=1,r;
    int a[1000005],d[1000005];
    int s[1000005];
    int e[1000005];
    long long q[1000005],p[1000005];
    using namespace std;

    int judge(int x,int temp)
    {
    int i,sum=0,b=0;
    if(temp==0) for(i=1;i<=x;i++) {q[s[i]]=q[s[i]]+d[i]; q[e[i]+1]=q[e[i]+1]-d[i];} //第一次加载,前缀和
    if(temp==1) for(i=l;i<=x;i++) {q[s[i]]=q[s[i]]+d[i]; q[e[i]+1]=q[e[i]+1]-d[i];}

    if(temp==2) for(i=x+1;i<=r+1;i++) {q[s[i]]=q[s[i]]-d[i]; q[e[i]+1]=q[e[i]+1]+d[i];} //防止重复加载
    for(i=1;i<=n;i++) {sum+=q[i]; p[i]=sum;}
    for(i=1;i<=n;i++) if(p[i]>a[i]) b=1; //线段树处理
    if(b==1) return 0;
    return 1;
    }

    int main()
    {

    int i,mid,ans=-1,z=0;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    for(i=1;i<=m;i++) scanf("%d %d %d",&d[i],&s[i],&e[i]);
    r=m;
    while(l<=r)
    {
    mid=(l+r)/2;
    if(judge(mid,z)) {ans=mid; l=mid+1; z=1;}
    else {r=mid-1; z=2;}
    } //二分订单
    if(ans==m) printf("0"); //全都行
    else {
    if(ans==-1) ans=0; //全不行
    printf("-1\n%d",ans+1); //中间开始不行
    }
    return 0;
    }

  • 0
    @ 2015-07-05 08:25:53

    懒标记线段树+读入优化 最高1600ms险过

    #include<stdio.h>
    struct segtree
    {
    int left,right,cover,mark;
    };

    struct segtree tree[6000010];

    int n,m,bools[1000000]={0},flag=0,minnum=1000000000;

    inline int read( )
    {
    int x=0;
    char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    x=0;
    while (ch<='9' && ch>='0')
    {
    x*=10,x+=ch-'0';
    ch=getchar();
    }
    return x;
    }

    int min(int a,int b)
    {
    if(a<b) return a;
    else return b;
    }

    void build(int p,int a,int b)
    {
    tree[p].left=a;
    tree[p].right=b;
    tree[p].mark=0;

    if(b-a>1)
    {
    build(p*2,a,(a+b)/2);
    build(p*2+1,(a+b)/2,b);
    tree[p].cover=min(tree[p*2].cover,tree[p*2+1].cover);
    }

    else tree[p].cover=bools[a];
    }

    void pushmark(int p)
    {
    tree[p*2].mark=tree[p*2].mark+tree[p].mark;
    tree[p*2+1].mark=tree[p*2+1].mark+tree[p].mark;
    tree[p*2].cover=tree[p*2].cover+tree[p].mark;
    tree[p*2+1].cover=tree[p*2+1].cover+tree[p].mark;
    tree[p].mark=0;
    }

    void insert(int p,int a,int b,int value)
    {

    if(a==tree[p].left && b==tree[p].right)

    {
    tree[p].cover=tree[p].cover+value;
    tree[p].mark=tree[p].mark+value;
    }

    else
    {
    int mid;
    mid=(tree[p].left+tree[p].right)/2;

    if(a>=mid)
    {
    pushmark(p);
    insert(p*2+1,a,b,value);
    tree[p].cover=min(tree[p].cover,tree[p*2+1].cover);
    }

    else if(b<=mid)
    {
    pushmark(p);
    insert(p*2,a,b,value);
    tree[p].cover=min(tree[p].cover,tree[p*2].cover);
    }

    else
    {
    pushmark(p);
    insert(p*2,a,mid,value);
    insert(p*2+1,mid,b,value);
    tree[p].cover=min(tree[p].cover,tree[p*2+1].cover);
    tree[p].cover=min(tree[p].cover,tree[p*2].cover);
    }

    }
    }

    void getmin(int p,int a,int b)
    {

    if(a==tree[p].left && b==tree[p].right)

    minnum=min(minnum,tree[p].cover);

    else
    {
    pushmark(p);
    int mid;
    mid=(tree[p].left+tree[p].right)/2;

    if(a>=mid)
    getmin(p*2+1,a,b);

    else if(b<=mid)
    getmin(p*2,a,b);

    else
    {
    getmin(p*2,a,mid);
    getmin(p*2+1,mid,b);
    }

    }
    }

    int main( )
    {

    int i,x1,x2,x3;

    n=read( );
    m=read( );

    for(i=1;i<=n;i++)
    bools[i]=read( );

    build(1,1,n+1);

    for(i=1;i<=m;i++)
    {
    x1=read( );
    x2=read( );
    x3=read( );
    insert(1,x2,x3+1,-x1);
    getmin(1,x2,x3+1);
    if(minnum<0) {printf("-1\n");printf("%d",i);flag=1;break;}

    }

    if(flag==0) printf("0");

    return 0;
    }

  • 0
    @ 2014-11-06 21:31:28

    评测机真坑!在本地1s不开优化AC,在这2s开O2TLE,醉了,醉了。。。
    #include<cstdio>
    #include<cstring>
    #include<algorithm>

    using namespace std;

    int tree[4000001],tag[4000001],num,day[1000001],tmp;

    inline int min(int a,int b) {
    return a<b?a:b;
    }

    inline void update(int pos) {
    if(tag[pos]==0) return;
    tag[pos<<1]+=tag[pos];
    tag[(pos<<1)+1]+=tag[pos];
    tree[(pos<<1)+1]+=tag[pos];
    tree[pos<<1]+=tag[pos];
    tag[pos]=0;
    }

    void insert(int pos,int l,int r,int ll,int rr,int delta) {
    if(ll<=l&&r<=rr) {
    tree[pos]+=delta;
    if(tree[pos]<0){
    printf("-1\n%d",num);
    exit(0);
    }
    tag[pos]+=delta;
    return;
    }
    update(pos);
    int mid=(l+r)>>1;
    if(ll<mid) insert(pos<<1,l,mid,ll,rr,delta);
    if(mid<rr) insert((pos<<1)+1,mid,r,ll,rr,delta);
    tree[pos]=min(tree[pos<<1],tree[(pos<<1)+1]);
    }

    void read(int &x) {
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    x=0;
    while(ch<='9'&&ch>='0'){
    x=x*10+ch-'0';
    ch=getchar();
    }
    }

    void build(int pos,int l,int r) {
    if(l+1==r){
    read(tmp);
    tree[pos]=tmp;
    return;
    }
    int mid=(l+r)>>1;
    build(pos<<1,l,mid);
    build((pos<<1)+1,mid,r);
    tree[pos]=min(tree[(pos<<1)+1],tree[pos<<1]);
    }

    int main() {
    int N,M,tmp;
    read(N);
    read(M);
    build(1,1,N+1);
    for(int i=1,d,s,t;i<=M;i++)
    {
    read(d);
    read(s);
    read(t);
    num=i;
    insert(1,1,N+1,s,t+1,-d);
    }
    putchar('0');
    return 0;
    }

    • @ 2015-02-24 16:31:37

      。。。
      我把你代码中read()加了inline然后就A了。。。
      。。。

  • 0
    @ 2014-08-01 23:25:33

    线段树+读入优化。。。

    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    int Min[4000006],Tag[4000006],M,n,m;
    const int INF=~0U>>2;
    void Down(int pos)
    {
    for (int k=M;k;k>>=1)
    {
    int s=pos/k;
    if (0==Tag[s] || s+s>M+M+M) continue;
    Tag[s<<1]+=Tag[s],Min[s<<1]+=Tag[s];
    Tag[(s<<1)^1]+=Tag[s],Min[(s<<1)^1]+=Tag[s];
    Tag[s]=0;
    }
    }
    void Up(int pos)
    {
    for (int i=pos>>1;i;i>>=1) Min[i]=min(Min[i<<1],Min[(i<<1)+1])+Tag[i];
    }
    int Get_Min(int l,int r)
    {
    int ans=INF;
    l=l+M-1,r=r+M+1;
    Down(l),Down(r);
    for (int s=l,t=r;s^1^t;s>>=1,t>>=1)
    {
    if (~s&1) ans=min(ans,Min[s^1]);
    if (t&1) ans=min(ans,Min[t^1]);
    }
    return ans;
    }
    void Add(int l,int r,int k)
    {
    l=l+M-1,r=r+M+1;
    Down(l),Down(r);
    for (int s=l,t=r;s^1^t;s>>=1,t>>=1)
    {
    if (~s&1) Tag[s^1]+=k,Min[s^1]+=k;
    if (t&1) Tag[t^1]+=k,Min[t^1]+=k;
    }
    Up(l),Up(r);
    }
    inline void Read(int &x)
    {
    char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    x=0;
    while (ch<='9' && ch>='0')
    {
    x*=10,x+=ch-'0';
    ch=getchar();
    }
    }
    int main()
    {
    scanf("%d%d",&n,&m);
    for (M=1;M<=n+1;M<<=1);
    for (int i=1;i<=n;i++) Read(Min[M+i]);//scanf("%d",Min+M+i);
    for (int i=M-1;i;i--) Min[i]=min(Min[(i<<1)+1],Min[i<<1]);
    for (int i=1,d,s,t;i<=m;i++)
    {
    Read(d),Read(s),Read(t);//scanf("%d%d%d",&d,&s,&t);
    int x=Get_Min(s,t);
    if (x<d)
    {
    puts("-1");
    printf("%d\n",i);
    return 0;
    }
    Add(s,t,-d);
    }
    puts("0");
    return 0;
    }

    • @ 2014-10-28 21:56:41

      不只是读入优化了→_→
      位运算什么。。。。。。。。

  • 0
    @ 2014-04-07 20:13:20

    #include<cstdio>
    #include<cstring>
    #define N 1000010
    using namespace std;
    struct lr{int l,r,num;}a[N];
    int lim[N],n,m,f[N];
    bool check(int x)
    {
    memset(f,0,sizeof(f));
    int ret=0,i;
    for(i=1;i<=x;++i)
    {
    f[a[i].l]+=a[i].num;
    f[a[i].r+1]-=a[i].num;
    }
    for(i=1;i<=n;++i)
    {
    ret+=f[i];
    if (ret>lim[i]) return 0;
    }
    return 1;
    }
    int main()
    {
    scanf("%d%d",&n,&m);
    int i,l,r,mid;
    for(i=1;i<=n;++i) scanf("%d",&lim[i]);
    for(i=1;i<=m;++i)
    scanf("%d%d%d",&a[i].num,&a[i].l,&a[i].r);
    l=1; r=m+1;
    while (l<r)
    {
    mid=l+r>>1;
    if (check(mid)) l=mid+1;
    else r=mid;
    }
    if (l>m) puts("0");
    else printf("-1\n%d",l);
    return 0;
    }

  • 0
    @ 2014-01-10 14:28:07

    给二分加了个奇怪的小剪枝就卡着时限过了

  • 0
    @ 2013-09-23 12:18:45

    这道题的测试数据不科学啊

  • 0
    @ 2013-08-19 15:59:25

    为什么我打的NOIP2012的AC程序到这儿就变95了?

  • 0
    @ 2013-07-19 16:04:35

    var
    n,m,i,l,r,now,k,ssum:longint;
    room,d,s,t,sum:array[0..1000001]of longint;
    flag:boolean;
    procedure init;
    begin
    read(n,m);
    for i:=1 to n do
    read(room[i]);
    for i:=1 to m do
    read(d[i],s[i],t[i]);
    end;
    procedure print;
    begin
    write(0);
    halt;
    end;
    procedure work;
    begin
    now:=0;
    l:=0;
    r:=m+1;
    repeat
    flag:=true;
    k:=(l+r)shr 1;
    if k>now then
    for i:=now+1 to k do
    begin
    inc(sum[s[i]],d[i]);
    dec(sum[t[i]+1],d[i]);
    end
    else
    for i:=k+1 to now do
    begin
    dec(sum[s[i]],d[i]);
    inc(sum[t[i]+1],d[i]);
    end;
    now:=k;
    ssum:=0;
    for i:=1 to n do
    begin
    inc(ssum,sum[i]);
    if ssum>room[i] then begin flag:=false; break; end;
    end;
    if flag then l:=k+1
    else r:=k;
    until l=r;
    if (k=m)and(flag) then print;
    writeln(-1);
    write(l);
    end;
    begin
    init;
    work;
    end.

  • 0
    @ 2013-05-04 13:59:16

    二分查找
    VijosEx via JudgeDaemon2/13.4.6.0 via libjudge
    编译成功

    测试数据 #0: Accepted, time = 19 ms, mem = 32036 KiB, score = 5
    测试数据 #1: Accepted, time = 3 ms, mem = 32040 KiB, score = 5
    测试数据 #2: Accepted, time = 5 ms, mem = 32040 KiB, score = 5
    测试数据 #3: Accepted, time = 2 ms, mem = 32040 KiB, score = 5
    测试数据 #4: Accepted, time = 7 ms, mem = 32044 KiB, score = 5
    测试数据 #5: Accepted, time = 5 ms, mem = 32040 KiB, score = 5
    测试数据 #6: Accepted, time = 35 ms, mem = 32036 KiB, score = 5
    测试数据 #7: Accepted, time = 31 ms, mem = 32040 KiB, score = 5
    测试数据 #8: Accepted, time = 31 ms, mem = 32044 KiB, score = 5
    测试数据 #9: Accepted, time = 35 ms, mem = 32044 KiB, score = 5
    测试数据 #10: Accepted, time = 31 ms, mem = 32040 KiB, score = 5
    测试数据 #11: Accepted, time = 27 ms, mem = 32040 KiB, score = 5
    测试数据 #12: Accepted, time = 31 ms, mem = 32040 KiB, score = 5
    测试数据 #13: Accepted, time = 31 ms, mem = 32040 KiB, score = 5
    测试数据 #14: Accepted, time = 309 ms, mem = 32036 KiB, score = 5
    测试数据 #15: Accepted, time = 317 ms, mem = 32040 KiB, score = 5
    测试数据 #16: Accepted, time = 313 ms, mem = 32040 KiB, score = 5
    测试数据 #17: Accepted, time = 313 ms, mem = 32040 KiB, score = 5
    测试数据 #18: Accepted, time = 317 ms, mem = 32040 KiB, score = 5
    测试数据 #19: Accepted, time = 309 ms, mem = 32040 KiB, score = 5
    Accepted, time = 2181 ms, mem = 32044 KiB, score = 100

    program classroom(input,output);
    var
    s,t,d,a:array[1..1000000] of longint;
    f:array[1..1000001] of int64;
    k:array[1..1000000] of int64;
    n,m:longint;
    z:longint;
    procedure init;
    var
    i:longint;
    begin
    assign(input,'classroom.in');
    assign(output,'classroom.out');
    reset(input);
    rewrite(output);
    readln(n,m);
    for i:=1 to n do
    read(a[i]);
    readln;
    for i:=1 to m do readln(d[i],s[i],t[i]);
    close(input);
    randomize;
    fillchar(f,sizeof(f),0);
    z:=0;
    fillchar(k,sizeof(k),0);
    end;
    function check(x:longint):boolean;
    var
    i:longint;
    begin
    if z<x then
    for i:=z+1 to x do
    begin
    f[s[i]]:=f[s[i]]+d[i];
    f[t[i]+1]:=f[t[i]+1]-d[i];
    end;
    if z>x then
    for i:=x+1 to z do
    begin
    f[s[i]]:=f[s[i]]-d[i];
    f[t[i]+1]:=f[t[i]+1]+d[i];
    end;
    z:=x;
    k[1]:=f[1];
    if k[1]>a[1] then exit(false);
    for i:=2 to n do
    begin
    k[i]:=k[i-1]+f[i];
    if k[i]>a[i] then exit(false);
    end;
    { for i:=1 to n do
    if k[i]>a[i] then exit(false);}
    exit(true);
    end;
    procedure out_put(x:longint);
    begin
    writeln(x);
    close(output);
    halt;
    end;
    procedure work;
    var
    j,i,x:longint;
    begin
    j:=m;
    if check(1)=false then
    begin writeln(-1); out_put(1); end;
    if check(m) then
    begin
    writeln(0);
    close(output);
    halt;
    end else writeln(-1);
    i:=0;
    while true do
    begin
    x:=(j-i+1) div 2+i;
    if check(x)=false then
    begin
    if (j-i=1) then out_put(j);
    if (x-i=1) then out_put(x);
    j:=x;
    end else
    begin
    if (j-i=1) then out_put(j);
    if (j-x=1) then out_put(j);
    i:=x;
    end;
    if (i=j) then out_put(i);
    end;
    end;
    begin
    init;
    work;
    end.

  • 0
    @ 2012-11-20 17:39:13

    sofa

  • -1
    @ 2016-11-17 16:06:57

    #include <cstdio>
    #include <cstring>
    #define O 1000100

    int n,m;
    int r[O],d[O],s[O],t[O];
    int pre[O];

    int check(int x){
    memset(pre,0,sizeof(pre));
    for(int i=1;i<=x;i++){
    pre[s[i]]+=d[i];
    pre[t[i]+1]-=d[i];
    }
    int now=0;
    for(int i=1;i<=n;i++){
    now+=pre[i];
    if(now>r[i])
    return 0;
    }
    return 1;
    }

    int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",&r[i]);
    for(int i=1;i<=m;i++)
    scanf("%d%d%d",&d[i],&s[i],&t[i]);
    int L=1,R=m,mid,ans=0;
    while(L<R){
    mid=(L+R)/2;
    if(!check(mid)){
    ans=mid;
    R=mid;
    }
    else
    L=mid+1;

    }
    if(ans==0)
    printf("0");
    else
    printf("-1\n%d",ans);
    return 0;
    }

  • -1
    @ 2016-11-02 01:55:00

    //输入很重要
    //用 cin ,ios::sync_with_stdio(false)cin,和scanf的结果差别很大!!!!!!!!!
    #include <iostream>
    #include <cstdio>
    #include <cstring>

    using namespace std;

    #define MAXN 1000001

    int n, m;

    int unc[MAXN];
    int dunc[MAXN], sunc[MAXN], tunc[MAXN];
    int twounc[MAXN];
    int notu = -1;

    inline int fin(int l, int r)
    {
    if (r <= l)return 0;
    int i, j;
    int mid = (l + r) / 2;
    bool key = true;
    //前缀和(简单而极其有效 6666)
    memset(twounc, 0, sizeof(twounc));
    for (j = 1; j <= mid; ++j)
    {
    twounc[sunc[j]] += dunc[j];
    twounc[tunc[j] + 1] -= dunc[j];
    }
    int sum = 0;
    for (i = 1; i <= n; ++i)
    {
    sum += twounc[i];
    if (sum > unc[i])goto A1;
    }
    key = false;
    A1:
    if (key)
    {
    notu = mid;
    fin(l, mid);
    }
    else fin(mid + 1, r);
    return 0;
    }

    int main()
    {
    // ios::sync_with_stdio(false);
    int i;
    scanf("%d %d", &n, &m);
    for (i = 1; i <= n; ++i)
    {
    scanf("%d", &unc[i]);
    }
    for (i = 1; i <= m; ++i)
    {
    scanf("%d %d %d", &dunc[i], &sunc[i], &tunc[i]);
    }
    fin(1, m);
    if (notu != -1)
    cout << -1 << endl << notu;
    else cout << 0;
    //system("pause");
    return 0;
    }

  • -1
    @ 2016-10-17 20:36:54

    二分订单+前缀和+读入优化=完美!>_<

  • -1
    @ 2016-10-17 19:56:32

    第一次独立的打对线段树!!!!!!!

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #define INF 0x3f3f3f3f
    using namespace std;
    struct node{
    int id,l,r,minin,lazy,numv;
    }tree[4*1000000];
    int n,m,num[1000005]={0},d,s,t;
    void read(int &x){
    char ch;
    int f=1;
    x=0;
    ch=getchar();
    while(ch<'0'||ch>'9'){
    if(ch=='-') f=-1;
    ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';
    ch=getchar();
    }
    }
    void build(int i,int l,int r){
    tree[i].l=l;tree[i].r=r;
    tree[i].lazy=0;tree[i].minin=INF;
    tree[i].numv=0;
    tree[i].id=i;
    if(l==r){
    num[l]=i;
    return;
    }
    int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build((i<<1)+1,mid+1,r);
    }
    void change(int i,int v){
    while(i>1){
    if(tree[i].l==tree[i].r){
    tree[i].minin=v;
    }
    int fa=i>>1;
    int left=fa<<1,right=(fa<<1)+1;
    tree[fa].minin=min(tree[fa].minin,tree[i].minin);
    i=fa;
    }
    return;
    }
    int check(int v,int sta,int to,int i,int l,int r){
    if(tree[i].lazy!=0&&l!=r){
    int left=i<<1,right=(i<<1)+1,u=tree[i].lazy;
    tree[left].minin-=u;tree[right].minin-=u;
    tree[left].lazy+=u;tree[right].lazy+=u;
    tree[i].lazy=0;
    }
    if(r<sta||l>to) return tree[i].minin;
    if(l>=sta&&r<=to){
    tree[i].minin-=v;
    tree[i].lazy+=v;
    return tree[i].minin;
    }
    else{
    int mid=(l+r)>>1;
    int tmp1=check(v,sta,to,i<<1,l,mid);
    int tmp2=check(v,sta,to,(i<<1)+1,mid+1,r);
    tree[i].minin=min(tmp1,tmp2);
    return tree[i].minin;
    }
    }
    int main(){
    freopen("classroom7.in","r",stdin);
    //freopen("classroom.out","w",stdout);
    int i,r;
    read(n);read(m);
    build(1,1,n);
    for(i=1;i<=n;i++){
    read(r);
    change(num[i],r);
    }
    for(i=1;i<=m;i++){
    read(d);read(s);read(t);
    int temp=check(d,s,t,1,1,n);
    if(temp<0){
    printf("-1\n%d",i);
    return 0;
    }
    }
    printf("0\n");
    return 0;
    }

  • -1
    @ 2016-09-28 21:28:09

    二分法 二分订单编号
    如果前mid个订单可行 l=mid+1
    否则 r=mid
    在这里特别注意边界的讨论 +1还是不加
    (前mid可行 所以不可行的只在mid+1后)
    (前mid不可行 不可行的可能包括mid 所以不-1)
    判断前x个可不可行 用前缀和......
    前缀和是个神奇的算法 但很好理解
    订单从i=1到x循环 在pre[start[i]]加上订单i的天数 并在pre[end[i]+1]减去订单i的天数
    开一个sum变量 表示当前正在使用的房间个数。
    循环 i=1 到 n ,sum+=pre[i]
    自然的,在start[i]天时就会加上所使用的房间,在end[i]+1天时就会自动减去它们
    注意大数组开在开头 如果开在函数内 会出错
    #include <cstdio>
    #include <cstring>
    #define Q 1000100

    int n,m,r[Q],d[Q],s[Q],t[Q],pre[Q];

    int g(){
    char p=' ';int x=0;
    while(!(p>='0'&&p<='9')) p=getchar();
    while(p>='0'&&p<='9') x=x*10+p-'0',p=getchar();
    return x;
    }

    int check(int x){
    int sum=0;
    memset(pre,0,sizeof(pre));
    for(int i=1;i<=x;i++)
    pre[s[i]]+=d[i],
    pre[t[i]+1]-=d[i];
    for(int i=1;i<=n;i++){
    sum+=pre[i];
    if(sum>r[i]) return 0;
    }

    return 1;
    }

    int main(){
    freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    r[i]=g();
    for(int i=1;i<=m;i++)
    d[i]=g(),s[i]=g(),t[i]=g();
    int L=1,R=m,mid,ans=0;
    while(L<R){
    mid=(L+R)/2;
    if(check(mid)==0)
    ans=mid,R=mid;
    else
    L=mid+1;
    }
    if(ans) printf("-1\n%d",ans);
    else printf("0");
    return 0;
    }

  • -1
    @ 2016-09-14 16:44:33
    评测结果
    编译成功
    
    测试数据 #0: Accepted, time = 0 ms, mem = 20080 KiB, score = 5
    测试数据 #1: Accepted, time = 0 ms, mem = 20076 KiB, score = 5
    测试数据 #2: Accepted, time = 0 ms, mem = 20076 KiB, score = 5
    测试数据 #3: Accepted, time = 0 ms, mem = 20080 KiB, score = 5
    测试数据 #4: Accepted, time = 15 ms, mem = 20076 KiB, score = 5
    测试数据 #5: Accepted, time = 0 ms, mem = 20084 KiB, score = 5
    测试数据 #6: Accepted, time = 156 ms, mem = 20080 KiB, score = 5
    测试数据 #7: Accepted, time = 140 ms, mem = 20072 KiB, score = 5
    测试数据 #8: Accepted, time = 171 ms, mem = 20080 KiB, score = 5
    测试数据 #9: Accepted, time = 156 ms, mem = 20080 KiB, score = 5
    测试数据 #10: Accepted, time = 140 ms, mem = 20080 KiB, score = 5
    测试数据 #11: Accepted, time = 156 ms, mem = 20076 KiB, score = 5
    测试数据 #12: Accepted, time = 140 ms, mem = 20080 KiB, score = 5
    测试数据 #13: Accepted, time = 171 ms, mem = 20076 KiB, score = 5
    测试数据 #14: Accepted, time = 1500 ms, mem = 20080 KiB, score = 5
    测试数据 #15: Accepted, time = 1453 ms, mem = 20080 KiB, score = 5
    测试数据 #16: Accepted, time = 1750 ms, mem = 20076 KiB, score = 5
    测试数据 #17: Accepted, time = 1656 ms, mem = 20076 KiB, score = 5
    测试数据 #18: Accepted, time = 1578 ms, mem = 20080 KiB, score = 5
    测试数据 #19: Accepted, time = 1734 ms, mem = 20076 KiB, score = 5
    Accepted, time = 10916 ms, mem = 20084 KiB, score = 100
    代码
    #include <cstring>
    #include <cstdio>
    int ans = 0,n,m,x[1000001],r[1000001],d[1000001],s[1000001],t[1000001];
    inline void find(int L,int R) {
      if (R <= L) return;
      int mid = (L+R)/2;
      bool flag = true;
      memset(x,0,sizeof(x));
      for (int i = 1;i <= mid;i++) {
        x[s[i]] += d[i];
        x[t[i]+1] -= d[i];
      }
      int sum = 0;
      for (int i = 1;i <= n;i++) {
        sum += x[i];
        if (sum > r[i]) {
          flag = false;
          break;
        }
      }
      if (!flag) {
        ans = mid;
        find(L,mid);
      } else find(mid+1,R);
    }
    int main() {
      //freopen("classroom.in","r",stdin);
      //freopen("classroom.out","w",stdout);
      scanf("%d%d",&n,&m);
      for (int i = 1;i <= n;i++) scanf("%d",&r[i]);
      for (int i = 1;i <= m;i++) scanf("%d%d%d",&d[i],&s[i],&t[i]);
      find(1,m);
      if (!ans) printf("0");
      else printf("-1\n%d",ans);
      return 0;
    }
    
  • -1
    @ 2016-09-06 16:18:03

    顺便*安利*一下我个人的**博客**:
    Haogram的博客:http://haogram.hol.es/
    谢谢。

信息

ID
1782
难度
8
分类
模拟 | 其他 | 二分查找数据结构 | 线段树 点击显示
标签
递交数
8240
已通过
1233
通过率
15%
被复制
12
上传者