一?問題描述

設有?n?家客戶，n<=31，每個客戶有如下屬性（客戶名稱、客戶類型、經度、緯度、每月拜訪次數）。

每個客戶 times 天拜訪 1 次。

每個客戶每天最多拜訪 8 次。

每月天數為 days。

求一個月拜訪軌跡。

二?輸入和輸出

1?輸入

第1行3個數用空行隔開：n times days 。

接下來的 n 行描述每個客戶，每個客戶信息包括（客戶名稱、客戶類型、經度、緯度、每月拜訪次數），客戶類型有：B-商業拜訪，H-醫院拜訪、P-藥房拜訪

2?輸出

藥代這個月每天拜訪軌跡。

三 輸入和輸出樣例

1?輸入樣例

31 3 31 H1 H 117.196067 39.103303 8 H2 H 117.206175 39.111509 8 H3 H 117.187551 39.109744 8 H4 H 117.179981 39.113295 8 H5 H 117.183536 39.125713 8 H6 H 117.209626 39.12228 8 H7 H 117.233087 39.082267 8 H8 H 117.195568 39.111846 8 H9 H 117.207421 39.121483 8 H10 H 117.191717 39.104914 8 H11 H 117.200753 39.109458 8 H12 H 117.182597 39.102957 8 H13 H 117.188228 39.128191 8 H14 H 117.193003 39.121008 8 H15 H 117.190858 39.135014 8 H16 H 117.179979 39.11038 8 M1 B 117.18461 39.117381 4 M2 B 117.206176 39.127932 4 M3 B 117.185073 39.124452 4 M4 B 117.183584 39.121472 4 M5 B 117.172522 39.126702 4 M6 B 117.185248 39.104909 4 M7 B 117.192618 39.129049 4 M8 B 117.181509 39.123574 4 P1 P 117.186092 39.130847 16 P2 P 117.212735 39.11644 16 P3 P 117.202735 39.11644 16 P4 P 117.206176 39.117932 16 P5 P 117.196367 39.103303 16 P6 P 117.209626 39.13228 16 P7 P 117.200653 39.109458 16

2?輸出樣例

1 號拜訪客戶：H7 > H1 > M6 > H16 > H4 > H13 > P1 > P4 > 2 號拜訪客戶：P5 > H11 > H2 > P2 > H14 > M4 > H5 > M7 > 3 號拜訪客戶：M2 > P6 > H6 > H9 > H15 > M8 > M5 > H3 > 4 號拜訪客戶：H10 > H1 > P7 > M6 > H4 > H13 > P1 > H7 > 5 號拜訪客戶：M7 > H5 > M4 > M1 > H8 > H11 > H2 > P5 > 6 號拜訪客戶：H12 > H3 > P3 > H9 > H6 > M2 > P6 > M5 > 7 號拜訪客戶：P1 > H13 > H4 > H16 > M6 > H1 > P7 > P4 > 8 號拜訪客戶：M7 > H5 > M1 > H14 > H8 > H2 > P2 > P5 > 9 號拜訪客戶：M8 > H15 > M2 > P6 > H6 > H9 > P3 > H3 > 10 號拜訪客戶：P7 > H1 > H10 > H16 > H4 > M3 > H13 > P4 > 11 號拜訪客戶：H8 > H11 > H2 > P2 > H14 > M1 > H5 > M7 > 12 號拜訪客戶：H3 > H12 > M5 > H15 > M2 > P6 > H6 > H9 > 13 號拜訪客戶：M3 > P1 > H4 > H10 > H1 > P7 > P4 > H7 > 14 號拜訪客戶：M4 > M1 > H14 > H5 > H8 > H11 > H2 > P2 > 15 號拜訪客戶：H15 > M8 > M5 > H3 > H12 > P3 > H6 > P6 > 16 號拜訪客戶：H4 > H16 > H10 > P7 > P4 > H13 > P1 > M3 > 17 號拜訪客戶：H8 > H11 > H2 > P2 > H14 > M4 > H5 > P5 > 18 號拜訪客戶：P3 > H9 > H6 > P6 > H15 > M8 > H3 > H12 > 19 號拜訪客戶：P7 > H1 > H10 > H16 > H4 > M3 > H13 > P1 > 20 號拜訪客戶：P5 > H11 > H8 > H2 > P2 > H14 > H5 > 21 號拜訪客戶：H15 > P6 > H6 > H9 > P3 > H3 > H12 > 22 號拜訪客戶：P7 > H1 > M6 > H16 > H4 > P1 > P4 > H7 > 23 號拜訪客戶：H14 > H5 > H8 > H11 > H2 > P2 > P5 > 24 號拜訪客戶：H9 > H6 > P3 > H3 > H12 > H15 > P6 > 25 號拜訪客戶：H16 > H10 > H1 > P7 > P4 > H13 > P1 > H7 > 26 號拜訪客戶：P5 > H11 > H8 > H14 > P2 > 27 號拜訪客戶：P6 > H9 > P3 > H12 > H15 > 28 號拜訪客戶：H13 > P1 > P4 > P7 > H10 > H16 > H7 > 29 號拜訪客戶：P2 > P5 > 30 號拜訪客戶：P6 > P3 > H12 > 31 號拜訪客戶：H10 > P7 > P4 > P1 > H7 >

四?代碼

package com.platform.modules.alg.alglib.sdgt0001;import java.util.*;public class Sdgt0001 {public String output = "";/*** 默認地球半徑*/private static double EARTH_RADIUS = 6371000; // 赤道半徑(單位m)private final int inf = 0x3f3f3f3f;// 客戶數private int n;// 拜訪頻率，幾天拜訪一次private int frequency;// 拜訪天數，每月拜訪多少天private int days;// 客戶批次 map，第1個泛型代表第幾批客戶，第2個泛型代表批次客戶列表private Map<Integer, List<Customer>> batchCustomerMap = new HashMap<>();// 拜訪軌跡 map，第1個泛型代表每月第幾天，第2個泛型代表該天拜訪的客戶列表private Map<Integer, List<Customer>> visitMap = new HashMap<>();// 軌跡計算public String cal(String input) {String[] line = input.split("\n");String[] params = line[0].split(" ");n = Integer.parseInt(params[0]); // 客戶數frequency = Integer.parseInt(params[1]); // 幾天拜訪一次days = Integer.parseInt(params[2]); // 每月拜訪多少天// 對輸入數據進行處理for (int i = 1; i <= n; i++) {String[] customerStr = line[i].split(" ");Customer customer = new Customer();customer.setName(customerStr[0]); // 客戶名稱customer.setType(customerStr[1]); // 客戶類別customer.setLocationLon(Double.parseDouble(customerStr[2])); // 經度customer.setLocationLat(Double.parseDouble(customerStr[3])); // 緯度customer.setTotalCount(Integer.parseInt(customerStr[4])); // 每月最多拜訪次數// 批次客戶列表加第1個客戶，如果 frequency = 3，則批次下標范圍 [0,1,2]if (batchCustomerMap.get(i % frequency) == null) {List<Customer> batchCustomerList = new ArrayList();batchCustomerList.add(customer);batchCustomerMap.put(i % frequency, batchCustomerList);} else { // 批次客戶列表加其他客戶batchCustomerMap.get((i % frequency)).add(customer);}}// 每日拜訪處理for (int i = 1; i <= days; i++) {// 批次下標號，處理第幾批客戶int batch = i % frequency;// 獲取某批次客戶列表List<Customer> customers = batchCustomerMap.get(batch);// 打亂批次客戶列表順序Collections.shuffle(customers);List<Customer> selectCustomers = new ArrayList<>();// 選擇前8個客戶for (int j = 0; j < customers.size(); j++) {if (customers.get(j).getTotalCount() > 0) {selectCustomers.add(customers.get(j));if (selectCustomers.size() >= 8) {break;}}}// 每日拜訪的第1個客戶if (selectCustomers.size() == 0) continue;Customer startCustomer = selectCustomers.get(0);// 標識該客戶已訪問startCustomer.setVisited(true);// 修正剩余可拜訪次數int plusCount = startCustomer.getTotalCount() - 1;startCustomer.setTotalCount(plusCount);// 創建第 i 號的拜訪客戶列表List<Customer> oneDayCustomerList = new ArrayList();visitMap.put(i, oneDayCustomerList);// 向 i 號拜訪客戶列表加第1個客戶oneDayCustomerList.add(startCustomer);Customer firstCustomer; // 兩次相鄰拜訪的前一個客戶Customer secondCustomer; // 兩次相鄰拜訪的后一個客戶Customer nextSelectCustomer = new Customer(); // 下一個選中的客戶double tempMinDistance; // 臨時最短距離firstCustomer = startCustomer;for (int m = 1; m < selectCustomers.size(); m++) { // 從第2個客戶開始處理double minDistance = inf; // 初始化最短距離for (int n = 1; n < selectCustomers.size(); n++) { // 從第2個客戶開始處理secondCustomer = selectCustomers.get(n);// 兩次相鄰拜訪的后一個客戶如果已經拜訪或剩余可拜訪次數為0，不處理if (secondCustomer.isVisited() || secondCustomer.getTotalCount() == 0) {continue;}// 計算相鄰兩個客戶的距離tempMinDistance = GetDistance(firstCustomer.getLocationLon(), firstCustomer.getLocationLat(), secondCustomer.getLocationLon(), secondCustomer.getLocationLat());if (tempMinDistance < minDistance) {// 更新最短距離minDistance = tempMinDistance;// 最短距離對應的客戶nextSelectCustomer = secondCustomer;}}// 下一個被選中的客戶設置為已拜訪nextSelectCustomer.setVisited(true);int plusTimes = nextSelectCustomer.getTotalCount() - 1;// 下一個被選中的客戶剩余拜訪次數nextSelectCustomer.setTotalCount(plusTimes);// 向 i 號拜訪客戶列表加選中的客戶visitMap.get(i).add(nextSelectCustomer);firstCustomer = nextSelectCustomer;}// visited 只對當天拜訪起作用，所以要清空 visited 標識for (Customer selectCustomer : customers) {selectCustomer.setVisited(false);}}// 輸出處理for (int i = 1; i <= days; i++) {List<Customer> customers = visitMap.get(i);if (customers == null) {continue;}output += i + " 號拜訪客戶：";for (Customer customer : customers) {output += customer.getName() + " > ";}output += "\n";}return output;}/*** 功能描述：通過經緯度計算兩點之間的距離** @param lon1 第 1 個點的經度* @param lat1 第 1 個點的緯度* @param lon2 第 2 個點經度* @param lat2 第 2 個點緯度* @return 兩點間的距離* @author chengqiuming* @date 2022/10/25* @description:*/public double GetDistance(double lon1, double lat1, double lon2, double lat2) {double radLat1 = rad(lat1);double radLat2 = rad(lat2);double a = radLat1 - radLat2;double b = rad(lon1) - rad(lon2);double s = 2 * Math.asin(Math.sqrt(Math.pow(Math.sin(a / 2), 2) + Math.cos(radLat1) * Math.cos(radLat2) * Math.pow(Math.sin(b / 2), 2)));s = s * EARTH_RADIUS;s = Math.round(s * 10000) / 10000;return s;}/*** 轉化為弧度(rad)*/private static double rad(double d) {return d * Math.PI / 180.0;} }class Customer {// 客戶名稱private String name;// 客戶類型 H-醫院客戶 M-商業公司客戶 P-藥房拜訪private String type;// 經度private Double locationLon;// 緯度private Double locationLat;// 每月最多可拜訪次數private int totalCount;// 是否已拜訪private boolean visited = false;public String getName() {return name;}public void setName(String name) {this.name = name;}public String getType() {return type;}public void setType(String type) {this.type = type;}public Double getLocationLon() {return locationLon;}public void setLocationLon(Double locationLon) {this.locationLon = locationLon;}public Double getLocationLat() {return locationLat;}public void setLocationLat(Double locationLat) {this.locationLat = locationLat;}public int getTotalCount() {return totalCount;}public void setTotalCount(int totalCount) {this.totalCount = totalCount;}public boolean isVisited() {return visited;}public void setVisited(boolean visited) {this.visited = visited;} }

五?測試

1?輸入

31 3 31

H1 H 117.196067 39.103303 8

H2 H 117.206175 39.111509 8

H3 H 117.187551 39.109744 8

H4 H 117.179981 39.113295 8

H5 H 117.183536 39.125713 8

H6 H 117.209626 39.12228 8

H7 H 117.233087 39.082267 8

H8 H 117.195568 39.111846 8

H9 H 117.207421 39.121483 8

H10 H 117.191717 39.104914 8

H11 H 117.200753 39.109458 8

H12 H 117.182597 39.102957 8

H13 H 117.188228 39.128191 8

H14 H 117.193003 39.121008 8

H15 H 117.190858 39.135014 8

H16 H 117.179979 39.11038 8

M1 B 117.18461 39.117381 4

M2 B 117.206176 39.127932 4

M3 B 117.185073 39.124452 4

M4 B 117.183584 39.121472 4

M5 B 117.172522 39.126702 4

M6 B 117.185248 39.104909 4

M7 B 117.192618 39.129049 4

M8 B 117.181509 39.123574 4

P1 P 117.186092 39.130847 10

P2 P 117.212735 39.11644 10

P3 P 117.202735 39.11644 10

P4 P 117.206176 39.117932 10

P5 P 117.196367 39.103303 10

P6 P 117.209626 39.13228 10

P7 P 117.200653 39.109458 10

2?輸出

1 號拜訪客戶：P4 > P7 > H10 > H16 > H4 > M3 > H13 > H7 >

2 號拜訪客戶：H5 > M7 > H14 > M1 > H8 > H11 > H2 > P2 >

3 號拜訪客戶：M2 > P6 > H6 > H9 > P3 > H3 > M8 > H15 >

4 號拜訪客戶：P7 > H1 > H10 > M6 > H4 > H13 > P1 > H7 >

5 號拜訪客戶：P2 > H2 > H11 > P5 > M1 > M4 > H14 > M7 >

6 號拜訪客戶：H6 > M2 > P6 > P3 > H3 > H12 > M8 > M5 >

7 號拜訪客戶：P4 > P7 > H10 > M6 > H16 > H4 > P1 > H7 >

8 號拜訪客戶：P5 > H8 > H2 > P2 > M7 > H5 > M4 > M1 >

9 號拜訪客戶：M5 > M8 > H3 > P3 > H9 > H6 > M2 > P6 >

10 號拜訪客戶：P1 > H13 > M3 > H4 > H16 > H10 > P7 > H7 >

11 號拜訪客戶：M4 > M1 > H14 > M7 > H5 > H11 > P5 > P2 >

12 號拜訪客戶：H15 > M8 > M5 > H12 > P3 > H9 > M2 > P6 >

13 號拜訪客戶：H4 > M6 > H10 > H1 > P7 > M3 > H13 > P1 >

14 號拜訪客戶：P5 > H11 > H2 > P2 > H8 > H14 > M4 > H5 >

15 號拜訪客戶：P3 > H9 > H6 > P6 > H15 > M5 > H3 > H12 >

16 號拜訪客戶：M6 > H16 > H4 > M3 > H13 > P4 > H1 > H7 >

17 號拜訪客戶：H14 > H5 > H8 > H11 > H2 > P2 > P5 >

18 號拜訪客戶：P6 > H6 > H9 > P3 > H3 > H12 > H15 >

19 號拜訪客戶：P1 > H13 > H4 > H10 > H1 > P7 > P4 > H7 >

20 號拜訪客戶：P2 > H2 > H11 > H8 > P5 > H14 > H5 >

21 號拜訪客戶：P6 > H6 > H9 > P3 > H3 > H12 > H15 >

22 號拜訪客戶：H10 > H1 > P7 > H16 > H4 > H13 > P1 > H7 >

23 號拜訪客戶：H5 > H14 > H8 > H11 > H2 > P2 > P5 >

24 號拜訪客戶：P3 > H9 > H6 > P6 > H15 > H3 > H12 >

25 號拜訪客戶：P7 > H1 > H10 > H16 > H13 > P1 > P4 > H7 >

26 號拜訪客戶：H8 > H11 > H2 > P2 > H14 > H5 > P5 >

27 號拜訪客戶：H3 > H12 > P3 > H9 > H6 > P6 > H15 >

28 號拜訪客戶：P4 > P7 > H1 > H16 > P1 >

29 號拜訪客戶：H8 > P5 > P2 >

30 號拜訪客戶：H12 > P3 > P6 > H15 >

31 號拜訪客戶：P1 > P4 > P7 > H1 > H16 >

總結

以上是生活随笔為你收集整理的基于经纬度的拜访轨迹问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。