京东笔试编程第二题考场安排

//考场安排 #include <iostream> #include <vector> #include <map> #include <queue> #include <list> #include <algorithm> using namespace std; //首先定义一个结构体 Peo: 编号 + 熟人链表 + 权值p（熟人个数） typedef struct Peo { int id; list<int> fri; int p; }Peo; int main() { int n, m; while (cin >> n >> m) { int x, y; //存放让出去考试的学生编号，最后按从小到大打印 vector<int> result; vector<Peo> v(2 * n + 1); for (int i = 0; i < 2 * n + 1; ++i) v[i].id = i; //初始化v中所有学生的id v[0].p = -9999; //v[0]仅为占位方便计算，p定义成-9999不会影响排序 for (int i = 0; i < m; ++i) { cin >> x >> y; //接收好友关系 //x的好友列表 + y //y的好友列表 + x //各自权值+1 v[x].fri.push_back(y); v[y].fri.push_back(x); v[x].p++; v[y].p++; } sort(v.begin(), v.end(), [](const Peo&a, const Peo&b) { return a.p > b.p; }); //按权值从小到大排序 while (1) { if (v[0].p <= 0) break; //如果排序后v[0]<0则意味着所有的熟人关系均已处理掉 if (v[0].p > 0) { for (auto &f : v[0].fri) { for (auto &e : v) { if (e.id == f) { --e.p; break; } } } v[0].p = 0; result.push_back(v[0].id); } sort(v.begin(), v.end(), [](const Peo&a, const Peo&b) { return a.p > b.p; }); } cout << result.size() << endl; for (auto e : result) { cout << e << endl; } } return 0; }

大概可以转化为这样一个问题 一个连通图，怎样删除图中最少的节点，使得边数为0

匈牙利算法，手写不出来

package JD; import java.util.Scanner; /**  * @Author: JackYe  * @CreateDate: 2019/8/24 20:22  * @Description: java类作用描述  * @UpdateUser: 更新者  * @UpdateDate: 2019/8/24 20:22  * @UpdateRemark: 更新说明  * @Version: 1.0  */ public class HTest02 {     public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);         int N = scanner.nextInt();         int M = scanner.nextInt();         int[][] relation = new int[N][N];         int[] all = new int[2*N];         for (int i = 0; i < M; i++) {             int male = scanner.nextInt();             int female = scanner.nextInt();             relation[male - 1][female - N - 1] = 1;             all[male-1]+=1;             all[female-1]+=1;         }         while (true){             int index= findMax(all);             if (all[index]==0) break;             all[index]=0;/*移除所有关系*/             System.out.println(index+1);             if(index<N){/*male*/                 for (int i=0;i<N;i++){                     if (relation[index][i]==1){                         all[N+i]--;                     }                 }             }             else {                 for (int i=0;i<N;i++){                     if (relation[i][index-N]==1){                         all[i]--;                     }                 }             }         }     }     private static int findMax(int[] all){         int index=0;         for (int i=1;i<all.length;i++){            if (all[i]>all[index]){                index=i;            }         }         return index;     }      } 本地测试了下还可以。

最小点覆盖 百度吧

匈牙利算法+Konig算法 https://www.nowcoder.com/discuss/233167

第一题ac，不用dp，并查集思路顺序遍历一遍就可以； 第二题本地过了，上去编译错误。。。最后没时间检查了，我分享一下思路，不知道对不对： 首先有个二维数组维护男女关系，一个坐标是男，另一个是女；然后有一个2n长度（也就是男女总和）的当前关系表，记录每个人（男或女）与当前教室里的人的关系数，表是个vector，每一项包含一对值（key:这个人的序号，value:剩余关系数）。 开始，将这张2n的表排序（从大到小，排序规则是根据value来排序，当value相同时，key小的在前），这样可以确保满足字典序。然后开始将数组第一个的同学记录下来，它的关系表清零，和它有关系的异性同学的关系数减一。然后重新排序这个2n的关系表，重复上面步骤，直到总关系数为零（用个变量记录它），然后输出记录即可。 在本地测了多种情况没有问题。。。但是不知道出了啥情况，提交上去编译出错。。。超郁闷

有个问题没想通 假如关系最复杂的那个男生出去了，接下来关系最复杂的女生也要出去，但她们两有关系，能一起出去吗

/* 男女编号[1,n] [n+1,2n]，映射到(n+1)X(n+1)矩阵， 第一列记录每个男生的关系总数，第一行记录每个女生的关系总数， arr[0][0]记录男女关系对数，为0表示无男女关系， 矩阵剩下的位置表示对应编号的男女关系：1存在、0不存在。 每次从第一列第一行找出关系最多的编号搬出，并移除他的关系，直到arr[0][0]==0  */ public class Main{     static int n;     static int[][] arr;     static List<Integer> list=new LinkedList<>();     public static void main(String[] args){         Scanner sc = new Scanner(System.in);         n=sc.nextInt();         arr=new int[n+1][n+1];         arr[0][0]=sc.nextInt();         for(int i=0;i<arr[0][0];i++){             int boyId=sc.nextInt();             int girlId=sc.nextInt();             arr[boyId][girlId-n]=1;             arr[boyId][0]+=1;             arr[0][girlId-n]+=1;         }         while (arr[0][0]!=0){             move();         }         //最后保证字典序最小         Collections.sort(list);         System.out.println(list.size());         System.out.println(list);     }     static void move(){         int maxId=-1,maxVal=0;         //找到关系最多的男或者女，且字典序最小         for(int i=1;i<=2*n;i++){             if(i<=n){                 if (arr[i][0]>maxVal){                     maxId=i;                     maxVal=arr[i][0];                 }             }else {                 if (arr[0][i-n]>maxVal){                     maxId=i;                     maxVal=arr[0][i-n];                 }             }         }         //搬出男或者女         //并且移除他和其他人的关系，同时减少关系对数         if(maxId<=n){             arr[maxId][0]=0;             for(int i=1;i<=n;i++){                 if(arr[maxId][i]==1){                     arr[0][i]--;                     arr[0][0]--;                 }             }         }else {             arr[0][maxId-n]=0;             for(int i=1;i<=n;i++){                 if(arr[i][maxId-n]==1){                     arr[i][0]--;                     arr[0][0]--;                 }             }         }         //记录本次搬出的编号         list.add(maxId);     } }

京东总共有几次笔试啊😁

用拓扑排序可以搞定考场安排，可以只过了36 ，没改完 刚刚改好 package demo4; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.Map; import java.util.Map.Entry; import java.util.Queue; import java.util.Scanner; import java.util.Set; public class Main7 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); Map<Integer, Integer> degree = new HashMap<>(); Map<Integer, Set<Integer>> map = new HashMap<>(); for (int i = 1; i <= 2 * n; i++) { degree.put(i, 0); } for (int i = 0; i < m; i++) { int a = sc.nextInt(); int b = sc.nextInt(); if (a > b) { int temp = b; b = a; a = temp; } if (map.containsKey(a)) { Set<Integer> set = map.get(a); set.add(b); map.put(a, set); degree.put(a, degree.get(a) + 1); degree.put(b, degree.get(b) + 1); } else { Set<Integer> set = new HashSet<>(); set.add(b); map.put(a, set); degree.put(a, degree.get(a) + 1); degree.put(b, degree.get(b) + 1); } } while (true) { int q = Integer.MIN_VALUE; int value = Integer.MIN_VALUE; boolean flag = false; for (int c : degree.keySet()) { if (degree.get(c) != Integer.MIN_VALUE && degree.get(c) != 0 && degree.get(c) > value) { q = c; value = degree.get(c); flag = true; } } if (flag == false) { break; } Integer integer = q; if (q <= n) { if (map.containsKey(integer)) { for (Integer c2 : map.get(integer)) { if (degree.get(c2) != integer.MIN_VALUE) degree.put(c2, degree.get(c2) - 1); } degree.put(integer, integer.MIN_VALUE); } } else { Set<Entry<Integer, Set<Integer>>> keySet = map.entrySet(); for (Entry<Integer, Set<Integer>> entry : keySet) { if (entry.getValue().contains(q)) { degree.put(entry.getKey(), degree.get(entry.getKey()) - 1); degree.put(q, degree.get(q) - 1); } } if (degree.get(q) == 0) { degree.put(q, integer.MIN_VALUE); } } } int sum = 0; ArrayList<Integer> arr = new ArrayList<>(); for (Integer integer : degree.keySet()) { if (degree.get(integer) == Integer.MIN_VALUE) { sum++; arr.add(integer); } } Collections.sort(arr); System.out.println(sum); for (int i = 0; i < arr.size() - 1; i++) { System.out.print(arr.get(i) + " "); } System.out.println(arr.get(arr.size() - 1)); } }

n, m = map(int,input().split()) nan_list = [] nv_list = [] dict_num = {} for i in range(m):     x,y = map(int,input().split())     nan_list.append(x)     nv_list.append(y) nan_dict = set(nan_list) nv_dict = set(nv_list) for i in nan_dict:     dict_num[i] = nan_list.count(i) for j in nv_dict:     dict_num[j] = nv_list.count(j) #print(dict_num) res = [] count = 0 for k,v in dict_num.items():     if v + count != m:         res.append(str(k))         count += v     else:         res.append(str(k))         break print(len(res)) print(' '.join(res)) 不知道对不对 没来得及测试

贪心对于这个例子应该不行 8 5 1 3  1 4 1 5 3 6 4 7 5 8 贪心应该是下面这样的 4 1 3 4 5 但是，1是可以在教室里的 3 3 4 5

第二题，输入n和m，然后输入的是m行对应朋友关系是吗？

import java.util.*; public class Demo02 {     public static class MyMap{         public TreeMap<Integer, HashSet<Integer>> _map;         public MyMap() {             this._map =new TreeMap<>();         }         void put(int maleNum, int femaleNum){             if(_map.containsKey(maleNum)){                 _map.get(maleNum).add(femaleNum);             }else {                 HashSet<Integer> tmp=new HashSet<>();                 tmp.add(femaleNum);                 _map.put(maleNum,tmp);             }         }         int getMaxLinkCount(){             int maxSize=0;             Set<Map.Entry<Integer, HashSet<Integer>>> entries = _map.entrySet();             for(Map.Entry<Integer, HashSet<Integer>> iter:entries){                 maxSize=Math.max(iter.getValue().size(),maxSize);             }             return maxSize;         }         int getMaxLinkKey(int maxSize){             Set<Map.Entry<Integer, HashSet<Integer>>> entries = _map.entrySet();             for(Map.Entry<Integer, HashSet<Integer>> iter:entries){                 if(iter.getValue().size()==maxSize){                     return iter.getKey();                 }             }             return -1;         }         Set<Integer> remove(int key){             Set<Integer> res=null;             if(_map.containsKey(key)){                 res=_map.remove(key);             }             return res;         }         void removeValue(int key,int value){             _map.get(key).remove(value);             if(_map.get(key).size()==0){                 _map.remove(key);             }         }     }     public static void main(String[] args) {         Scanner in=new Scanner(System.in);         int n=in.nextInt();         int m=in.nextInt();         MyMap maleMap=new MyMap();         MyMap femaleMap=new MyMap();         for(int i=0;i<m;i++){             int tmp1=in.nextInt();             int tmp2=in.nextInt();             maleMap.put(tmp1,tmp2);             femaleMap.put(tmp2,tmp1);         }         int count=0;         ArrayList<Integer> res=new ArrayList<>();         while (maleMap._map.size()>0){             count++;             int max1=maleMap.getMaxLinkCount();             int max2=femaleMap.getMaxLinkCount();             int max=Math.max(max1,max2);             MyMap toRemove=max1<max2?femaleMap:maleMap;             int key=toRemove.getMaxLinkKey(max);             Set<Integer> set=toRemove.remove(key);             MyMap another=max1<max2?maleMap:femaleMap;             for(int iter:set){                 another.removeValue(iter,key);             }             res.add(key);         }         System.out.println(count);         Collections.sort(res);//这句话当时忘加了。。。a了9%         for(int iter:res){             System.out.println(iter);         }     } }

36😆

第二题9🤣

第一题55超时。第二题根本想不会。。。

第一题18，然后没时间做第二题凉凉😂

36 36注定做不了东哥兄弟了