人寿研发笔试第三题
划分机器人家族
整体思路——贪心算法
一个家族区间[l,r]合法的条件:所有相邻两数差的绝对值的gcd(最大公约数)不等于1,且区间内没有重复的元素
题目让求划分家族的最少数量,因此先明确需要新增家族的几种情况:
需要新增家族的三种情况:
- 相邻的两个数差为0或1是不行的,会新增家族;
- 一样的数不能出自一个厂家,用map标记
- 相邻两个差值的gcd不能等于1,否则也会新增家族
其他情况直接将当前元素加入当前家族
import java.util.*; import java.lang.*; public class Main{ static int[] nums; static Map<Integer,Integer> map = new HashMap<>(); //辗转相除法求最大公约数 public static int func(int a, int b){ while(b!=0){ int tmp = a%b; a=b; b=tmp; } return a; } public static void main(String[] args) { int n; Scanner sc = new Scanner(System.in); n = sc.nextInt(); nums = new int[n+2]; for(int i=1; i<=n; i++){ nums[i] = sc.nextInt(); } nums[n+1] = 0; int sum=1; int p=0; p = Math.abs(nums[2]-nums[1]); map.put(nums[1],1); for(int i=2; i<=n; i++){ if(map.containsKey(nums[i]) && map.get(nums[i])==1){ //2.相同的数不能来自一个家族 for(Iterator iterator = map.keySet().iterator(); iterator.hasNext();){ int next = (int)iterator.next(); iterator.remove(); } map.put(nums[i],1); sum++; p=Math.abs(nums[i+1]-nums[i]); continue; } if(p==0 || p==1){ //1.如果相邻两个数的差为1或者0,应该新增家族 for(Iterator iterator = map.keySet().iterator(); iterator.hasNext();){ int next = (int)iterator.next(); iterator.remove(); } map.put(nums[i],1); sum++; p=Math.abs(nums[i+1]-nums[i]); continue; } //3.下面判断相邻两个差值的gcd是否等于1 int q = Math.abs(nums[i]-nums[i-1]); if(q==0 || q==1){ for(Iterator iterator = map.keySet().iterator(); iterator.hasNext();){ int next = (int)iterator.next(); iterator.remove(); } map.put(nums[i],1); sum++; p=Math.abs(nums[i+1]-nums[i]); continue; } if(func(q,p) == 1){ //如果当前差值和前面的最大公约数为1,应当新增家族 for(Iterator iterator = map.keySet().iterator(); iterator.hasNext();){ int next = (int)iterator.next(); iterator.remove(); } map.put(nums[i],1); sum++; p=Math.abs(nums[i+1]-nums[i]); } else{ //如果满足gcd>1那么直接把这个机器人加到这个厂里,并把新的gcd当成比较对象 p=func(q,p); map.put(nums[i],1); } } System.out.println(sum); } }#Java开发##中国人寿研发中心##笔经#