比赛题意:

300:

一套零件要1~m每种各一样,现在有n个工厂

第i个工厂能生产k_i个零件,编号必须在a_i到b_i之间

问最多能组多少套

题解:二分答案,然后就没了吧

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
map<int,int> ma;
bool check(int x,int m,vector <int> k, vector <int> a, vector <int> b)
{
    if ((long long)x*m>50000000) return false;
    int n=k.size();
    map<int,int>::iterator ii;
    for (ii=ma.begin();ii!=ma.end();ii++)
    {
        map<int,int>::iterator jj;
        jj=ii;
        jj++;
        if ((*ii).first==m+1) return true;
        int sum=((*jj).first-(*ii).first)*x;
        for (;;)
        {
            int i;
            int t=-1;
            for (i=0;i<n;i++)
            {
                if ((a[i]<=(*ii).first)&&((*ii).first<=b[i])&&(k[i]>0))
                {
                    if (t==-1)
                    {
                        t=i;
                    }
                    else if (b[i]<b[t])
                    {
                        t=i;
                    }
                }
            }
            if (t==-1) return false;
            if (k[t]<sum)
            {
                sum-=k[t];
                k[t]=0;
            }
            else
            {
                k[t]-=sum;
                break;
            }
        }
    }
    return true;
}
struct FleetFunding
{
    int maxShips(int m, vector <int> k, vector <int> a, vector <int> b)
    {
        int n=k.size();
        int i;
        ma[1]=1;
        ma[m+1]=1;
        for (i=0;i<n;i++)
        {
            ma[a[i]]=1;
            ma[b[i]+1]=1;
        }
        int l=1,r=50000005;
        for (;l<=r;)
        {
            int mid=(l+r)/2;
            if (check(mid,m,k,a,b)) l=mid+1; else r=mid-1;
        }
        return r;
    }
};
#ifdef absi2011
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    
    return 0;
}
#endif