Code Jam 2017 Round 1A Problem B. Ratatouille

传送门

分析

首先把包（package）的克数 $Q_{ij}$ 转化成区间 $[\lceil Q_{ij}/(1.1 r_i )\rceil, \lfloor Q_{ij}/(0.9 r_i)\rfloor]$。可以通过将分子、分母同乘10来避免精度问题。注意某个包对应的区间可能为空，比如 $Q_{ij}=13, r_i=10$。然后将每种成分（ingredient）的包对应的区间按左右端点双关键字从小到大排序（用std::pair<int,int>表示区间）。考虑 $n$ 个最小的区间，两两比较，若不相交则将较小的区间删除（该区间对应的包不可能存在于任何 kit 中）。重复此删除过程，直到最小的 $n$ 个区间交集不为空。用这 $n$ 个区间对应的包组成一个 kit。

这个做法的正确性可通过如下性质证明：

Implementation

#include <bits/stdc++.h>

using namespace std;

int T;

int cas;

const int N=55;

int r[N];

int q[N][N];

using P=pair<int,int> ;

int main(){

    for(cin>>T; T--; ){

        printf("Case #%d: ", ++cas); // ！注意输出格式

        ///////////////////////////////////////

        int  n, p;

        cin >> n >> p;

        priority_queue<P, vector<P>, greater<P>> que[N];

        for(int i=0; i<n; i++)

            cin >> r[i];

        for(int i=0; i<n; i++)

            for(int j=0; j<p; j++){

                cin >> q[i][j];

                int mi=10*q[i][j]/(11*r[i])+bool(10*q[i][j]%(11*r[i]));

                int ma=q[i][j]*10/(9*r[i]);

                if(mi>ma) continue;

                que[i].push({mi, ma});

                // cout << mi <<' ' << ma<<endl;

            }

        // for(int i=0; i<n; i++){

        //     auto x=que[i].top();

        //     cout << x.first<<' '<< x.second << endl;

        // }

        int res=0;

        for(;;){

            bool flag=true;

            for(int i=0; i<n; i++)

                if(que[i].empty()){

                    flag=false;

                    break;

                }

            if(!flag) break;

            bool f=true;

            for(int i=0; i<n; i++){

                for(int j=i+1; j< n; j++){

                    auto a=que[i].top(), b=que[j].top();

                    if(a.first>b.second){

                        que[j].pop();

                        f=false;

                        break;

                    }

                    if(b.first>a.second){

                        que[i].pop();

                        f=false;

                        break;

                    }

                }

                if(f==false) break;

            }

            if(f==false)

                continue;

            res++;

            for(int i=0; i<n; i++)

                que[i].pop();

        }

        cout << res<<endl;

////////////////////////////////////////////////////////

    }

    return 0;

}