Chinaunix首页 | 论坛 | 博客

竹子

首页　| 　博文目录　| 　关于我

bl竹子

  • 博客访问： 492665
  • 博文数量： 25
  • 博客积分： 111
  • 博客等级： 民兵
  • 技术积分： 1279
  • 用 户 组： 普通用户
  • 注册时间： 2012-10-26 20:51
文章分类

全部博文（25）

文章存档

2014年（17）

2013年（8）

我的朋友
最近访客
推荐博文
相关博文
编程之美---格格取数问题的贪心解法

分类： C/C++

2014-04-13 14:25:24

本文主要是对2014微软编程之美的一道题(格格取数)的解答，用的是贪心算法。问题如下：

给你一个m x n (1 <= m, n <= 100)的矩阵A (0<=aij<=10000)，要求在矩阵中选择一些数，要求每一行，每一列都至少选到了一个数，使得选出的数的和尽量的小。

本算法主要分两步，作简要说明：1、为了是每行每列都去到，我们分别对每行每列取最小值；2、在取得这些数值中可能存在多余的数值，对于这些数值我们进行两种处理：(1)看看可不可以直接删除，(2)看看可不可以进行转换

点击(此处)折叠或打开

  1. #include <iostream>
  2. #include <vector>
  3. #include <map>

  5. using namespace std;

  7. int row,col;
  8. vector<int> m_row,m_col;
  9. vector<vector<int> >matrix;
  10. vector<vector<bool> >mark;
  11. multimap<int,vector<pair<size_t,size_t> > >delete_map;

  13. void find_row_min_num(void){
  14.     for(int i=0;i<row;++i){
  15.         vector<int>& tmp_arr = matrix[i];
  16.         int tmp = matrix[i][0];
  17.         int k = 0;
  18.         for(int j=0;j<col;++j){
  19.             if(tmp > tmp_arr[j]){
  20.                 tmp = tmp_arr[j];
  21.                 k = j;
  22.             }
  23.         }
  24.         mark[i][k] = true;
  25.         //min_num.insert(make_pair(tmp,i*row+k));
  26.     }
  27. }

  29. void find_col_min_num(void){
  30.     for(int j=0;j<col;++j){
  31.         int tmp = matrix[0][j];
  32.         int k = 0;
  33.         for(int i=0;i<row;++i){
  34.             if(tmp > matrix[i][j]){
  35.                 tmp = matrix[i][j];
  36.                 k = i;
  37.             }
  38.         }
  39.         if(false == mark[k][j]){
  40.             mark[k][j] = true;
  41.             //min_num.insert(make_pair(tmp,k*row+j));
  42.         }
  43.     }
  44. }
  45. void mark_fix(int i,int pre){
  46.     //首先检查是否可以直接删除
  47.     for(int k=0;k<row;++k){
  48.         if(mark[k][pre] && k != i){
  49.             mark[i][pre] = false;
  50.             return;
  51.         }
  52.     }

  54.     for(int ii=i+1;ii<row;++ii){
  55.         if(mark[ii][pre])
  56.             continue;
  57.         if(matrix[ii][pre] == matrix[i][pre]){//同一列中有相同的最小值
  58.             for(int jj=0;jj<col;++jj){
  59.                 if(mark[ii][jj]){
  60.                     for(int iii=0;iii<row;++iii){//看看栓出此列是否合法
  61.                         if(mark[iii][jj]){
  62.                             if(iii != ii){
  63.                                 mark[ii][jj] = false;
  64.                                 mark[i][pre] = false;
  65.                                 mark[ii][pre] = true;
  66.                                 return;
  67.                             }
  68.                         }
  69.                     }
  70.                 }
  71.             }
  72.         }
  73.     }
  74. }

  76. void check_row(void){
  77.     for(int i=0;i<row;++i){
  78.         int pre = -1;
  79.         for(int j=0;j<col;++j){
  80.             if(mark[i][j]){
  81.                 if(-1 != pre){
  82.                     mark_fix(i,pre);
  83.                 }
  84.                 pre = j;
  85.             }
  86.         }
  87.         int count =0;
  88.         for(int k=0;k<col;++k){
  89.             if(mark[i][k])
  90.                 ++count;
  91.         }
  92.         if(count>1)
  93.             mark_fix(i,pre);
  94.     }
  95. }
  96. void delete_elem(void){
  97.     check_row();
  98. }
  99. void check_row_and_col(void){
  100.     for(int i=0;i<row;++i){
  101.         bool b = false;
  102.         for(int j=0;j<col;++j){
  103.             if(mark[i][j])
  104.                 if(!b)
  105.                     b = true;
  106.                 else{
  107.                     m_row.push_back(i);
  108.                     break;
  109.                 }
  110.         }
  111.     }
  112.     
  113.     for(int i=0;i<col;++i){
  114.         bool b = false;
  115.         for(int j=0;j<row;++j){
  116.             if(mark[j][i])
  117.                 if(!b)
  118.                     b = true;
  119.                 else{
  120.                     m_col.push_back(i);
  121.                     break;
  122.                 }
  123.         }
  124.     }
  125. }
  126. void fix_matrix(void){
  127.     check_row_and_col();
  128.     if(m_row.empty() || m_col.empty())
  129.         return;
  130.     for(size_t i=0;i<m_row.size();++i){
  131.         int max_num = 0;
  132.         int tmp_row = m_row[i];
  133.         vector<pair<size_t,size_t> > pairs;
  134.         for(int k=0;k<col;++k){
  135.             if(mark[tmp_row][k]){
  136.                 int tmp = matrix[tmp_row][k];
  137.                 for(size_t j=0;j<m_col.size();++j){
  138.                     int tmp_col = m_col[j];
  139.                     for(int kk=0;kk<row;++kk){
  140.                         if(mark[kk][tmp_col]){
  141.                             if(kk!=tmp_row && k!=tmp_col){
  142.                                 int a1 = matrix[kk][k];
  143.                                 int a2 = matrix[tmp_row][k];
  144.                                 int a3 = matrix[kk][tmp_col];
  145.                                 if(a1< a2+a3 && a2+a3-a1 > max_num){
  146.                                     max_num = a2+a3-a1;
  147.                                     pairs.clear();
  148.                                     pairs.push_back(make_pair(tmp_row,k));
  149.                                     pairs.push_back(make_pair(kk,tmp_col));
  150.                                 }
  151.                             }
  152.                         }
  153.                     }
  154.                 }
  155.             }
  156.         }
  157.         if(!pairs.empty())
  158.             delete_map.insert(make_pair(max_num,pairs));
  159.     }
  160. }
  161. bool adjust_elem(void){
  162.     if(delete_map.empty()){
  163.         delete_elem();
  164.         return true;
  165.     }
  166.     else{
  167.         for(multimap<int,vector<pair<size_t,size_t> > >::reverse_iterator riter = delete_map.rbegin();
  168.             riter != delete_map.rend();++riter){
  169.                 vector<pair<size_t,size_t> > tmp= riter->second;
  170.                 size_t a1 = tmp[0].first;
  171.                 size_t a2 = tmp[0].second;
  172.                 size_t a3 = tmp[1].first;
  173.                 size_t a4 = tmp[1].second;
  174.                 if(mark[a1][a4])
  175.                     if(matrix[a1][a2]+matrix[a3][a4]-matrix[a3][a2]<matrix[a1][a4]){
  176.                         mark[a1][a4] = false;
  177.                         continue;
  178.                     }
  179.                 if(mark[a1][a2] && mark[a3][a4]){
  180.                     mark[a1][a2] = mark[a3][a4] = false;
  181.                     mark[a3][a2] =true;
  182.                 }
  183.         }
  184.         delete_map.clear();
  185.         m_row.clear();
  186.         m_col.clear();
  187.         return false;
  188.     }
  189. }
  190. void find_min_sum(){
  191.     find_row_min_num();
  192.     find_col_min_num();

  194.     bool b = false;
  195.     while(!b){
  196.         fix_matrix();
  197.         b = adjust_elem();
  198.     }
  199. }
  200. int every_group(void){
  201.     cin>>row>>col;
  202.     for(int i=0;i<row;++i){
  203.         vector<int>tmp_arr;
  204.         vector<bool>tmp_mark;
  205.         for(int j=0;j<col;++j){
  206.             int tmp=0;
  207.             cin>>tmp;
  208.             tmp_arr.push_back(tmp);
  209.             tmp_mark.push_back(false);
  210.         }
  211.         matrix.push_back(tmp_arr);
  212.         mark.push_back(tmp_mark);
  213.     }

  215.     find_min_sum();

  217.     int sum=0;
  218.     for(int i=0;i<row;++i){
  219.         for(int j=0;j<col;++j){
  220.             if(true == mark[i][j]){
  221.                 sum += matrix[i][j];
  222.             }
  223.         }
  224.     }
  225.     matrix.clear();
  226.     mark.clear();
  227.     m_row.clear();
  228.     m_col.clear();
  229.     row=col=0;
  230.     return sum;
  231. }
  232. int main(){
  233.     int group_num;
  234.     cin>>group_num;
  235.     vector<int> vec;
  236.     for(int i=0;i<group_num;++i)
  237.         vec.push_back(every_group());

  239.     for(size_t i=0;i< vec.size();++i){
  240.         std::cout<<"Case "<<i+1<<": "<<vec[i]<<endl;
  241.     }

  243.     return 0;
  244. }

阅读(4062) | 评论(2) | 转发(0) |
1

上一篇：Nginx简单实例

下一篇：GDA和Logistic方法的区别及相应的python代码

给主人留下些什么吧！~~

bl竹子2014-04-16 10:34:15

hilcj0001：Hello度娘上搜到po主的
你这个方法我也想过了，不过还是不行的。
看下面这组数据，正确结果应该是选10 11 10 11 10=52，你的代码输出55。
10 99 99 99 99 
99 10 99 11 99
99 99 10 10 10
99 11 10 15 99
99 99 10 99 15

嗯，问题出在我的变换上了，我只对那些同行和同列存在多余一个元素的上，并没有进行全局调整，呵呵。贪心算法吗，很难得到最优解的（据说可以通过拟阵证明，但我是一直没看懂啊）当时提交，就AC了

回复 | 举报

hilcj00012014-04-16 10:08:27

Hello度娘上搜到po主的
你这个方法我也想过了，不过还是不行的。
看下面这组数据，正确结果应该是选10 11 10 11 10=52，你的代码输出55。
10 99 99 99 99 
99 10 99 11 99
99 99 10 10 10
99 11 10 15 99
99 99 10 99 15

回复 | 举报
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6