贪心算法实现从电台的问题

谁借莪１个温暖的怀抱￠ 2022-12-01 15:38 64阅读 0赞

#include <iostream>
    #include <algorithm>
    #include <set>
    #include <string>
    #include <iterator>
    #include <vector>
    #include <map>
    #include <functional>
    using namespace std;
    
    
    int main09()
    { 
    	map<string, set<string>> broadcast;
    
    	set<string> Set1;
    	Set1.insert("北京");
    	Set1.insert("上海");
    	Set1.insert("天津");
    
    	set<string> Set2;
    	Set2.insert("北京");
    	Set2.insert("广州");
    	Set2.insert("深圳");
    
    	set<string> Set3;
    	Set3.insert("成都");
    	Set3.insert("上海");
    	Set3.insert("杭州");
    
    
    	set<string> Set4;
    	Set4.insert("上海");
    	Set4.insert("天津");
    
    	set<string> Set5;
    	Set5.insert("杭州");
    	Set5.insert("大连");
    
    	broadcast.insert(pair<string, set<string>>("K1", Set1));
    	broadcast.insert(pair<string, set<string>>("K2", Set2));
    	broadcast.insert(pair<string, set<string>>("K3", Set3));
    	broadcast.insert(pair<string, set<string>>("K4", Set4));
    	broadcast.insert(pair<string, set<string>>("K5", Set5));
    
    	set<string> allAreas;
    	allAreas.insert("北京");
    	allAreas.insert("上海");
    	allAreas.insert("广州");
    	allAreas.insert("天津");
    	allAreas.insert("深圳");
    	allAreas.insert("成都");
    	allAreas.insert("杭州");
    	allAreas.insert("大连");
    
    	vector<string> selects;
    	//定义一个临时的集合来存放该电台和未地区之间的交集
    	set<string> tmpSet;
    	string maxKey = "";
    	int num = 0;
    	while (allAreas.size() > 0) { 
    		for (auto &bbb : broadcast)
    		{ 
    			set<string> areas = bbb.second;
    			set_intersection(allAreas.begin(), allAreas.end(), areas.begin(), areas.end(), \
    				inserter(tmpSet, tmpSet.begin()));
    			if (tmpSet.size() > 0 && (maxKey == "" || tmpSet.size() > num))
    			{ 
    				maxKey = bbb.first;
    				num = tmpSet.size();
    			}
    			tmpSet.clear();
    		}
    		selects.push_back(maxKey);
    		auto iter = broadcast.find(maxKey);
    		if (iter != broadcast.end())
    		{ 
    			set<string> tmpSet1;
    			set_difference(allAreas.begin(), allAreas.end(), iter->second.begin(), \
    				iter->second.end(), inserter(tmpSet1, tmpSet1.begin()));
    			allAreas = tmpSet1;
    			broadcast.erase(iter);
    		}
    		maxKey = "";
    		num = 0;
    	}
    	vector<int> itsMy{  1,2,4,5,6,10 };
    	cout << count_if(itsMy.begin(), itsMy.end(), not1(bind2nd(less<int>(), 10))) << endl;
    	copy(selects.begin(), selects.end(), ostream_iterator<string>(cout, ","));
    	not1(bind2nd(less<int>(), 10))(5);
    	return 0;
    }