首页 > 代码库 > ACM——01排序

ACM——01排序

2024-07-13 12:23:11   222人阅读

http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1024

01排序

时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte
总提交:708            测试通过:258

描述

将01串首先按长度排序，长度相同时，按1的个数多少进行排序，1的个数相同时再按ASCII码值排序。

输入

输入数据中含有一些01串，01串的长度不大于256个字符。

输出

重新排列01串的顺序。使得串按基本描述的方式排序。

样例输入

10011111
00001101
1010101
1
0
1100

样例输出

0
1
1100
1010101
00001101
10011111

题目来源

ZJUT

 

 1 #include<iostream> 2 #include<string> 3 //#include<fstream> 4 #include<vector> 5 using namespace std; 6 class Node 7 { 8 public: 9     string str;10     int len;11     int oneNum;12     Node(string s)13     {14         str = s;15         this->len = str.length();16         int tmp = 0;17         for (size_t i = 0; i<len; i++)18         if (str[i] == ‘1‘) tmp++;19         oneNum = tmp;20     }21 };22 23 int cmp(Node& node1, Node& node2)//-1表示node1排在前面0表示node1和node2相等1表示node1排在node2后面24 {25     if (node1.len<node2.len)26         return -1;27     else if (node1.len>node2.len) return 1;28     else //长度相等29     {30         if (node1.oneNum == node2.oneNum)//一的数目相等31         {32             size_t i;33             for (i = 0; i<node1.len; i++){//比较ASCLL码值34                 if (node1.str[i]<node2.str[i]) return -1;35                 else if (node1.str[i]>node2.str[i]) return 1;36             }37             if (i == node1.oneNum) return 0;//二者相等38         }39         else if (node1.oneNum<node2.oneNum) return -1;40         else //node1中1的数目比node2的多41             return 1;42     }43     return 0;44 }45 int main()46 {47     //ifstream ifile("D:\\eee.txt");48     string str;49     vector<Node> nVec;50     while (cin>>str)51     {52         Node node(str);53         if (true == nVec.empty())54             nVec.push_back(node);55         else56         {57             vector<Node>::iterator iter = nVec.begin();58             for (iter; iter != nVec.end(); iter++){59                 if (cmp(*iter, node) == 1){60                     nVec.insert(iter, node);61                     break;62                 }63                 if (cmp(*iter, node) == 0){64                     nVec.insert(iter, node);65                     break;66                 }67                 if (cmp(*iter, node) == -1)68                     ;69                 if (iter == nVec.end()-1){70                     //nVec.insert(iter, node);71                     nVec.push_back(node);72                     break;73                 }74 75             }76 77         }78     }79     for (size_t i = 0; i<nVec.size(); i++)80     {81         cout << nVec[i].str << endl;82     }83     return 0;84 }

 

 

 


联系
我们