POJ 2376：Cleaning Shifts

/*
    用区间去覆盖长为T的整条线段，求最少的区间数量
*/
#include <cstdio>
#include <algorithm>
using namespace std;
int d=0,pos,x,y,n,T,a[1000005];
int main(){
    scanf("%d%d",&n,&T);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        a[x]=max(a[x],y+1);
    }a[T+1]=T+1; 
	  for(int i=2;i<=T;i++)a[i]=max(a[i-1],a[i]);
    for(pos=1;a[pos]!=pos;pos=a[pos])d++;
    if(pos!=T+1)puts("-1");else printf("%d
",d);
    return 0;
}

POJ 1328：Radar Installation

/*
    在二维平面内给出一些点，现在允许你画圆心在x周上，半径固定的圆，
    求最小的圆个数，使得能将所有给出的点覆盖
*/
#include <cstdio>
#include <algorithm>
#include <cmath> 
using namespace std;
int n,Cas=0,flag,cnt; double r,x,y;
struct data{double l,r;}p[2005],tmp;
bool cmp(data a,data b){return a.l<b.l;}
int main(){
    while(scanf("%d%lf",&n,&r),n||r){
        flag=0;
        for(int i=0;i<n;i++){
            scanf("%lf%lf",&x,&y);
            if(fabs(y)>r)flag=1;
            else{
                p[i].l=x-sqrt(r*r-y*y);
                p[i].r=x+sqrt(r*r-y*y);
            }
        }printf("Case %d: ",++Cas);
        if(flag){puts("-1");}
        else{
            cnt=1;
            sort(p,p+n,cmp);
            tmp=p[0];
            for(int i=1;i<n;i++){
                if(p[i].l>tmp.r){
                    cnt++;
                    tmp=p[i];
                }else if(p[i].r<tmp.r)tmp=p[i];
            }printf("%d
",cnt);
        }
    }return 0;
}

POJ 3190：Stall Reservations

/*
    每头牛都有一段固定长度的时间要吃草，不能和别的牛重叠，
    现在问需要多少草槽才能满足所有牛的需求
*/
#include <cstdio>
#include <utility>
#include <queue>
#include <algorithm>
using namespace std;
struct data{int r,id;}tmp;
struct data1{int l,r,id;}p[50005];
int ans[50005],n,cnt;
bool operator<(data a,data b){return a.r>b.r;}
bool cmp(data1 a,data1 b){return a.l<b.l;}
int main(){
    priority_queue<data> Q;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d%d",&p[i].l,&p[i].r),p[i].id=i;
    sort(p,p+n,cmp);
    ans[p[0].id]=cnt=1;
    tmp.id=1;tmp.r=p[0].r;
    Q.push(tmp);
    for(int i=1;i<n;i++){
        tmp=Q.top();
        if(tmp.r<p[i].l){
            Q.pop();
            tmp.r=p[i].r;
            ans[p[i].id]=tmp.id;
            Q.push(tmp);
        }else{
            ans[p[i].id]=++cnt;
            tmp.r=p[i].r;
            tmp.id=cnt;
            Q.push(tmp);
        }
    }printf("%d
",cnt);
    for(int i=0;i<n;i++)printf("%d
",ans[i]);
    return 0;
}

POJ 2393：Yogurt factory

/*
    每周生产的牛奶所需要的费用为ci，保存每单位的牛奶每周需要费用为s，
    现在告诉你每周需要的牛奶数量，求最小的花费
*/
#include <cstdio>
#include <algorithm> 
using namespace std;
int n,s,c,y;
long long ans;
int main(){
    scanf("%d%d",&n,&s);
    int cost=5000;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&c,&y);
        cost=min(cost+s,c);
        ans+=cost*y;
    }printf("%lld
",ans);
    return 0;
}

POJ 1017：Packets

/*
    箱子的长宽是6*6，现在有一些6*6,5*5,4*4,3*3,2*2,1*1的物品
    问最少需要多少箱子才能把他们全都装下
*/
#include <cstdio>
int ans,a1,a2,a3,a4,a5,a6,lft;
int main(){
    while(~scanf("%d%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5,&a6),a1+a2+a3+a4+a5+a6){
        ans=(a5+a6+a4)+(a3+3)/4;
        lft=a4*5;
        if(a3%4)lft+=7-2*(a3%4);
        if(a2>lft)ans+=(a2-lft+8)/9;
        lft=ans*36-a6*36-a5*25-a4*16-a3*9-a2*4;
        if(a1>lft)ans+=(a1-lft+35)/36;
        printf("%d
",ans);
    }return 0;
}

POJ 3040：Allowance

/*
    给出你所拥有的面值不同的钞票数量，问你可以支付多少次大于等于c的费用
    钞票的面值为倍数关系（倍数关系可满足拟阵的遗传性质，因此贪心方法成立）
*/
#include <cstdio>
#include <algorithm>
#include <utility>
#include <climits>
#include <cstring> 
using namespace std;
#define ff first 
#define ss second 
const int INF=INT_MAX;
pair<int,int> p[25];
int n,C,ans,tag[25];
int main(){
    scanf("%d%d",&n,&C);
    for(int i=1;i<=n;i++)scanf("%d%d",&p[i].ff,&p[i].ss);
    sort(p+1,p+n+1);
    while(n&&p[n].ff>=C)ans+=p[n--].ss;  
    while(1){
        int s=C;
        memset(tag,0,sizeof(tag));
        for(int i=n;i;i--){
            int t=s/p[i].ff;
            t=min(t,p[i].ss);
            s-=t*p[i].ff;
            tag[i]+=t;
        }
        if(s){
            for(int i=1;i<=n;i++){
                if(p[i].ss&&p[i].ff>=s){
                	s=-0;
                	tag[i]++;
                	break;
                }
            }
       }if(s>0)break;
       int tmp=INF;
       for(int i=1;i<=n;i++){
           if(tag[i])tmp=min(tmp,p[i].ss/tag[i]);
       }ans+=tmp;
       for(int i=1;i<=n;i++)p[i].ss-=tmp*tag[i];
    }printf("%d
",ans);
    return 0;
}

POJ 1862：Stripies

/*
    质量为m1和m2的物品相碰之后。质量变为2*sqrt(m1*m2)，请你决定一种碰撞顺序
    使得碰撞之后答案最小。
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std; 
double a[105];
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
    sort(a+1,a+n+1);
    for(int i=n-1;i;i--)a[n]=2*sqrt(a[n]*a[i]);
    printf("%.3f
",a[n]);
    return 0;
}

POJ 3262：Protecting the Flowers

/*
    一些牛在花园啃话，每时间单位啃花di单位，将一头牛送牛棚再回来需要时间2*ti
    请最小化花朵被啃食的数量。

    若i和j两头牛位置相邻，则i在j前面消耗为(T+ti)*dj+T*di
    j在i前面消耗为(T+tj)*di+T*dj
    则i和j两头牛i牛在送回顺序中排在前面答案更优的充要条件为di*tj>dj*ti
*/
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
struct data{int t,d;}p[100010];
bool cmp(data a,data b){return a.d*b.t>b.d*a.t;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&p[i].t,&p[i].d);
    sort(p+1,p+n+1,cmp);
    long long ans=0,T=0;
    for(int i=1;i<=n;i++){
        ans+=T*p[i].d;
        T+=p[i].t*2;
    }printf("%lld
",ans);
    return 0;
}