HOJ 003 童話故事

[二分搜]

#include<stdio.h>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define LL long long int
#define MM 1000000
#define MAX(a,b) (((a)>(b)) ? (a):(b))
LL N;
LL VAL[MM];
LL DIS[MM];
bool Check(LL a)
{
    //printf("Check(%I64d)\n",a);
    LL Center=0;
    bool OK=true;
    for(int lx=0;lx<N;lx++)
        if(VAL[lx]>=a)
            Center+=MAX(VAL[lx]-a-DIS[lx],0);

    for(int lx=0;(lx<N)&&OK;lx++)
    {
        if(VAL[lx]<a)
            Center-=a-VAL[lx]+DIS[lx];
        OK=(Center>=0);
    }
    return OK;
}
int main()
{
    scanf("%I64d",&N);
    LL min=-1,max=0,mid;
    for(LL lx=0;lx<N;lx++)
    {
        scanf("%I64d %I64d",&DIS[lx],&VAL[lx]);
        if((min==-1)||(min>VAL[lx])) min=VAL[lx];
        max+=VAL[lx];
    }
    max/=N;
    while(min<max)
    {
        //printf("min=%I64d max=%I64d\n",min,max);
        if(min==max-1)
        {
            if(Check(max))
                min=max;
            break;
        }
        mid=(min+max)>>1;
        if(Check(mid))
            min=mid;
        else
            max=mid-1;
    }
    printf("%I64d\n",min);
    return 0;
}

HOJ 001 Problem : 1 - Breakfast

[無]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>


int main()
{
    int inp;
    while((scanf("%d",&inp)!=EOF) && inp )
    {
        if((inp==1)||(inp==2)||(inp==4)||(inp==7))
        {
            printf("This is Kongming's Trap!!!\n");
            continue;
        }
        int a,b,k;
        if(inp%3==0){a=inp/3;b=0;}
        if(inp%3==1){a=(inp-10)/3;b=2;}
        if(inp%3==2){a=(inp-5)/3;b=1;}
        k=a/5;
        a-=5*k;
        b+=3*k;
        printf("%d\n",a+b);
    }
    return 0;
}

HOJ 002 Problem 2 - 要我寫毛阿

[STACK括弧匹配]
今天拿到HSNU的帳號就先寫吧XDD
O(N)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct point
{
    int pos;
    int index;
};
struct line
{
    int a;int b;
    int index;
};
bool operator<(const line& x,const line& y)
{
    if(x.a<y.a)
        return true;
    if(x.a>y.a)
        return false;
    return (x.b<y.b);
}
bool operator==(const line& x,const line& y)
{
    return ((x.a==y.a)&&(x.b==y.b));
}
bool operator<(const point& x,const point& y)
{
    return (x.pos<y.pos);
}
point ps[200000];
line ls[100000];
line lsp[100000];
int stk[200000];
int main()
{
    int T;scanf("%d",&T);

    for(int lT=1;lT<=T;lT++)
    {
        int n;scanf("%d",&n);
        for(int lx=0;lx<n;lx++)
        {
            scanf("%d %d",&lsp[lx].a,&lsp[lx].b);
            lsp[lx].index=lx;
        }
        sort(lsp,lsp+n);
        //去除重複
        int cnt=1; ls[0]=lsp[0];
        for(int lx=1;lx<n;lx++)
        {
            if(lsp[lx]==lsp[lx-1]) continue;
            ls[cnt]=lsp[lx];cnt++;
        }
        //for(int lx=0;lx<cnt;lx++)
        //  printf("%d %d %d\n",ls[lx].a,ls[lx].b,lx);
        for(int lx=0;lx<cnt;lx++)
        {
            ps[lx*2].pos=ls[lx].a;
            ps[lx*2].index=lx;
            ps[lx*2+1].pos=ls[lx].b;
            ps[lx*2+1].index=lx;
        }
        sort(ps,ps+cnt*2);
        //for(int lx=0;lx<cnt*2;lx++)
        //  printf("%d %d\n",ps[lx].pos,ps[lx].index);

        int stkcnt=0;
        for(int lx=0;lx<cnt*2;lx++)
        {
            if(stkcnt==0)
            {
                stk[0]=ps[lx].index;
                stkcnt++;
            }
            else
            {
                if(stk[stkcnt-1]==ps[lx].index)
                    stkcnt--;
                else
                    stk[stkcnt++]=ps[lx].index;
            }
            //printf("stkcnt=%d\n",stkcnt);
        }
        if(stkcnt==0)
            printf("Y\n");
        else
            printf("N\n");
    }
}