POJ 1018 【枚举+剪枝】.cpp

题意：

　　给出n个工厂的产品参数带宽b和价格p，在这n个工厂里分别选1件产品共n件，使B/P最小，其中B表示n件产品中最小的b值，P表示n件产品p值的和。

　　输入 iCase n

　　　　表示iCase个样例n个工厂
　　　　m1 p1 b1 p2 b2..pm1 bm1 //第一个工厂有m1个同种类不同参数的产品，每一个产品的参数分别是p1 b1 p2 b2
　　　　m2 p1 b1 p2 b2..pm2 bm2
　　　　...
　　　　mn p1 b1 p2 b2..pmn bmn

思路：

　　排序，先把b从小到大排序，然后把p从小到大排序，最后让第几个工厂的序号从小到大排序

　　排完后就可以直接枚举了，枚举bi，固定了bi之后就枚举pj，取每一个工厂里满足bj比bi大的就加起来，然后计算哪一个值最大..

Tip：

其中有一些优化就是剪枝：

　　　　①. 因为最后肯定要有n个bj比bi大，所以bi枚举到sum-(n-1)就可以了，sum表示总共有多少个产品..

　　　　②. 如果枚举到bi比某一个公司的所有产品的b都大的时候，就不用往后枚举了，因为产品是按b排过序的，题目要求n-1个公司里面选取的b都要比当前bi大，既然当前bi比某一个公司的所有b都大了，则该公司无法选取符合条件的产品，而后面产品b都比bi大，就跟不可能选取到符合条件的产品了，所以就可以直接break;

　　　　③. 如果枚举到某一个bi的时候，bj比bi大的公司个数不满n个的话bi后面的b也可以不枚举了，原因同上..

Code：

 #include <stdio.h>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int MAXN = ;

 struct Div

 {

     int id;

     int p;

     int b;

 }_div[MAXN*MAXN];

 int maxB[MAXN];

 int cmp(Div a, Div b)

 {

     if (a.b != b.b) return a.b < b.b;

     else if (a.p != b.p) return a.p < b.p;

     else return a.id < b.id;

 }

 int main()

 {

    // freopen("in.txt", "r", stdin);

     int iCase, n, m, sum;

     //int vis;

     bool vis[MAXN];

     double ans;

     bool flag;

     scanf("%d", &iCase);

     while (iCase--) {

         sum = ans = ;

         memset(maxB, , sizeof(maxB));

         flag = true;

         scanf("%d", &n);

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

             scanf("%d", &m);

             while (m--) {

                 scanf("%d %d", &_div[sum].b, &_div[sum].p);

                 maxB[i] = max(maxB[i], _div[sum].b);

                 _div[sum++].id = i;

             }

         }

         sort(_div, _div+sum, cmp);

         for (int i = ; i < sum-(n-); ++i) {

             int P = _div[i].p;

             int count = ;

        //    vis = (1<<n)-1;

          //   vis ^= (1<<_div[i].id);

             memset(vis, false, sizeof(vis));

             vis[_div[i].id] = true;

             for (int j = i+; j < sum; ++j)

            //     if (vis & (1<<_div[j].id)) {

                 if (!vis[_div[j].id]) {

                     if (maxB[_div[j].id] < _div[i].b) {

                         flag = false;

                         break;

                     }

                     P += _div[j].p;

                     //vis ^= (1<<_div[j].id);

                     vis[_div[j].id] = true;

                     count++;

                 }

             if (count < n || !flag) break;

             ans = max(ans, (double)_div[i].b/P);

         }

         printf("%.3lf\n", ans);

     }

     return ;

 }

链接：http://poj.org/problem?id=1018

巴特西

POJ 1018 【枚举+剪枝】.cpp

最新文章

热门文章