一?問題描述

設(shè)有 n 家客戶，n <= 24，每個(gè)客戶有如下屬性（客戶名稱、客戶類型、經(jīng)度、緯度、每月拜訪次數(shù)）。

每個(gè)客戶?m?天拜訪 1 次。

每個(gè)客戶每天最多拜訪 8 次。

給出一個(gè)月的工作日列表。

求一個(gè)月拜訪軌跡。

二?輸入和輸出

1?輸入說明

第 1?行代表客戶數(shù)?n 和拜訪頻率 m。

接下來的 n 行描述每個(gè)客戶，每個(gè)客戶信息包括（客戶名稱、客戶類型、經(jīng)度、緯度、每月拜訪次數(shù)），客戶類型有：M-商業(yè)拜訪，H-醫(yī)院拜訪、P-藥房拜訪

接下來的一行是工作日列表

2?輸出說明

藥代這個(gè)月每天拜訪軌跡。

三?輸入和輸出樣例

1?輸入樣例

24 3

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

1 2 3 4 5 7 8 9 10 11 12 14 15 16 17 18 19 21 22 23 24 25 26 28 29 30

2?輸出樣例

1 號(hào)拜訪客戶：H9 > H6 > M2 > H15 > M8 > M5 > H3 > H12 >

2 號(hào)拜訪客戶：H4 > H16 > M6 > H10 > H1 > M3 > H13 > H7 >

3 號(hào)拜訪客戶：M7 > H5 > M4 > M1 > H14 > H8 > H11 > H2 >

4 號(hào)拜訪客戶：M2 > H6 > H9 > H15 > M8 > M5 > H3 > H12 >

5 號(hào)拜訪客戶：H1 > H10 > M6 > H16 > H4 > M3 > H13 > H7 >

7 號(hào)拜訪客戶：H14 > M4 > M1 > H5 > M7 > H8 > H11 > H2 >

8 號(hào)拜訪客戶：H15 > M8 > M5 > H3 > H12 > H9 > H6 > M2 >

9 號(hào)拜訪客戶：H7 > H1 > H10 > M6 > H16 > H4 > M3 > H13 >

10 號(hào)拜訪客戶：H5 > M4 > M1 > H14 > M7 > H8 > H11 > H2 >

11 號(hào)拜訪客戶：H12 > H3 > M8 > M5 > H15 > M2 > H6 > H9 >

12 號(hào)拜訪客戶：H7 > H1 > H10 > M6 > H16 > H4 > M3 > H13 >

14 號(hào)拜訪客戶：H8 > H11 > H2 > H14 > M4 > M1 > H5 > M7 >

15 號(hào)拜訪客戶：H6 > H9 > H15 > H3 > H12 >

16 號(hào)拜訪客戶：H7 > H1 > H10 > H16 > H4 > H13 >

17 號(hào)拜訪客戶：H8 > H11 > H2 > H14 > H5 >

18 號(hào)拜訪客戶：H3 > H12 > H9 > H6 > H15 >

19 號(hào)拜訪客戶：H16 > H4 > H10 > H1 > H13 > H7 >

21 號(hào)拜訪客戶：H8 > H11 > H2 > H14 > H5 >

22 號(hào)拜訪客戶：H9 > H6 > H15 > H3 > H12 >

23 號(hào)拜訪客戶：H13 > H4 > H16 > H10 > H1 > H7 >

24 號(hào)拜訪客戶：H5 > H14 > H8 > H11 > H2 >

25 號(hào)拜訪客戶：H3 > H12 > H9 > H6 > H15 >

26 號(hào)拜訪客戶：H4 > H16 > H10 > H1 > H13 > H7 >

28 號(hào)拜訪客戶：H8 > H11 > H2 > H14 > H5 >

四?代碼

package com.platform.modules.alg.alglib.sdgt0002;import java.util.*;public class Sdgt0002 {public String output = "";/*** 默認(rèn)地球半徑*/private static double EARTH_RADIUS = 6371000; // 赤道半徑(單位m)private final int inf = 0x3f3f3f3f;// 客戶數(shù)private int n;// 拜訪頻率，幾天拜訪一次private int frequency;// 拜訪天數(shù)，每月拜訪多少天private int days;// 客戶批次 map，第1個(gè)泛型代表第幾批客戶，第2個(gè)泛型代表批次客戶列表private Map<Integer, List<Customer>> batchCustomerMap = new HashMap<>();// 拜訪軌跡 map，第1個(gè)泛型代表每月第幾天，第2個(gè)泛型代表該天拜訪的客戶列表private Map<Integer, List<Customer>> visitMap = new HashMap<>();// 軌跡計(jì)算public String cal(String input) {String[] line = input.split("\n");String[] params = line[0].split(" ");n = Integer.parseInt(params[0]); // 客戶數(shù)frequency = Integer.parseInt(params[1]); // 幾天拜訪一次//days = Integer.parseInt(params[2]); // 每月拜訪多少天// 對(duì)輸入數(shù)據(jù)進(jìn)行處理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])); // 經(jīng)度customer.setLocationLat(Double.parseDouble(customerStr[3])); // 緯度customer.setTotalCount(Integer.parseInt(customerStr[4])); // 每月最多拜訪次數(shù)// 批次客戶列表加第1個(gè)客戶，如果 frequency = 3，則批次下標(biāo)范圍 [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);}}// 模擬每月的幾號(hào)String[] days = line[n + 1].split(" ");List batchDays[] = new ArrayList[frequency];for (int i = 0; i < batchDays.length; i++) {batchDays[i] = new ArrayList();}for (int i = 0; i < days.length; i++) {int batchNum = i % frequency;batchDays[batchNum].add(days[i]);}// 每日拜訪處理for (int i = 0; i < days.length; i++) {int batch = 0;for (List batchDay : batchDays) {if (batchDay.contains(days[i])) {batch = i % frequency;break;}}// 獲取某批次客戶列表List<Customer> customers = batchCustomerMap.get(batch);// 打亂批次客戶列表順序Collections.shuffle(customers);List<Customer> selectCustomers = new ArrayList<>();// 選擇前8個(gè)客戶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個(gè)客戶if (selectCustomers.size() == 0) continue;Customer startCustomer = selectCustomers.get(0);// 標(biāo)識(shí)該客戶已訪問startCustomer.setVisited(true);// 修正剩余可拜訪次數(shù)int plusCount = startCustomer.getTotalCount() - 1;startCustomer.setTotalCount(plusCount);// 創(chuàng)建第 i 號(hào)的拜訪客戶列表List<Customer> oneDayCustomerList = new ArrayList();visitMap.put(i, oneDayCustomerList);// 向 i 號(hào)拜訪客戶列表加第1個(gè)客戶oneDayCustomerList.add(startCustomer);Customer firstCustomer; // 兩次相鄰拜訪的前一個(gè)客戶Customer secondCustomer; // 兩次相鄰拜訪的后一個(gè)客戶Customer nextSelectCustomer = new Customer(); // 下一個(gè)選中的客戶double tempMinDistance; // 臨時(shí)最短距離firstCustomer = startCustomer;for (int m = 1; m < selectCustomers.size(); m++) { // 從第2個(gè)客戶開始處理double minDistance = inf; // 初始化最短距離for (int n = 1; n < selectCustomers.size(); n++) { // 從第2個(gè)客戶開始處理secondCustomer = selectCustomers.get(n);// 兩次相鄰拜訪的后一個(gè)客戶如果已經(jīng)拜訪或剩余可拜訪次數(shù)為0，不處理if (secondCustomer.isVisited() || secondCustomer.getTotalCount() == 0) {continue;}// 計(jì)算相鄰兩個(gè)客戶的距離tempMinDistance = GetDistance(firstCustomer.getLocationLon(), firstCustomer.getLocationLat(), secondCustomer.getLocationLon(), secondCustomer.getLocationLat());if (tempMinDistance < minDistance) {// 更新最短距離minDistance = tempMinDistance;// 最短距離對(duì)應(yīng)的客戶nextSelectCustomer = secondCustomer;}}// 下一個(gè)被選中的客戶設(shè)置為已拜訪nextSelectCustomer.setVisited(true);int plusTimes = nextSelectCustomer.getTotalCount() - 1;// 下一個(gè)被選中的客戶剩余拜訪次數(shù)nextSelectCustomer.setTotalCount(plusTimes);// 向 i 號(hào)拜訪客戶列表加選中的客戶visitMap.get(i).add(nextSelectCustomer);firstCustomer = nextSelectCustomer;}// visited 只對(duì)當(dāng)天拜訪起作用，所以要清空 visited 標(biāo)識(shí)for (Customer selectCustomer : customers) {selectCustomer.setVisited(false);}}// 輸出處理for (int i = 0; i < days.length; i++) {List<Customer> customers = visitMap.get(i);if (customers == null) {continue;}output += days[i] + " 號(hào)拜訪客戶：";for (Customer customer : customers) {output += customer.getName() + " > ";}output += "\n";}return output;}/*** 功能描述：通過經(jīng)緯度計(jì)算兩點(diǎn)之間的距離** @param lon1 第 1 個(gè)點(diǎn)的經(jīng)度* @param lat1 第 1 個(gè)點(diǎn)的緯度* @param lon2 第 2 個(gè)點(diǎn)經(jīng)度* @param lat2 第 2 個(gè)點(diǎn)緯度* @return 兩點(diǎn)間的距離* @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;}/*** 轉(zhuǎn)化為弧度(rad)*/private static double rad(double d) {return d * Math.PI / 180.0;} }class Customer {// 客戶名稱private String name;// 客戶類型 H-醫(yī)院客戶 M-商業(yè)公司客戶 P-藥房拜訪private String type;// 經(jīng)度private Double locationLon;// 緯度private Double locationLat;// 每月最多可拜訪次數(shù)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;} }

五?測(cè)試

1?輸入

24 3

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

1 2 3 4 5 7 8 9 10 11 12 14 15 16 17 18 19 21 22 23 24 25 26 28 29 30

2?輸出

1 號(hào)拜訪客戶：H15 > M8 > M5 > H3 > H12 > H9 > H6 > M2 >

2 號(hào)拜訪客戶：H1 > H10 > M6 > H16 > H4 > M3 > H13 > H7 >

3 號(hào)拜訪客戶：H14 > M4 > M1 > H5 > M7 > H8 > H11 > H2 >

4 號(hào)拜訪客戶：M2 > H6 > H9 > H15 > M8 > M5 > H3 > H12 >

5 號(hào)拜訪客戶：H13 > M3 > H4 > H16 > M6 > H10 > H1 > H7 >

7 號(hào)拜訪客戶：H14 > M4 > M1 > H5 > M7 > H8 > H11 > H2 >

8 號(hào)拜訪客戶：H6 > H9 > M2 > H15 > M8 > M5 > H3 > H12 >

9 號(hào)拜訪客戶：M3 > H13 > H4 > H16 > M6 > H10 > H1 > H7 >

10 號(hào)拜訪客戶：M1 > M4 > H5 > M7 > H14 > H8 > H11 > H2 >

11 號(hào)拜訪客戶：M8 > M5 > H15 > M2 > H6 > H9 > H3 > H12 >

12 號(hào)拜訪客戶：M3 > H13 > H4 > H16 > M6 > H10 > H1 > H7 >

14 號(hào)拜訪客戶：H8 > H11 > H2 > H14 > M4 > M1 > H5 > M7 >

15 號(hào)拜訪客戶：H15 > H9 > H6 > H3 > H12 >

16 號(hào)拜訪客戶：H7 > H1 > H10 > H16 > H4 > H13 >

17 號(hào)拜訪客戶：H5 > H14 > H8 > H11 > H2 >

18 號(hào)拜訪客戶：H12 > H3 > H9 > H6 > H15 >

19 號(hào)拜訪客戶：H1 > H10 > H16 > H4 > H13 > H7 >

21 號(hào)拜訪客戶：H11 > H2 > H8 > H14 > H5 >

22 號(hào)拜訪客戶：H9 > H6 > H15 > H3 > H12 >

23 號(hào)拜訪客戶：H4 > H16 > H10 > H1 > H13 > H7 >

24 號(hào)拜訪客戶：H2 > H11 > H8 > H14 > H5 >

25 號(hào)拜訪客戶：H12 > H3 > H9 > H6 > H15 >

26 號(hào)拜訪客戶：H1 > H10 > H16 > H4 > H13 > H7 >

28 號(hào)拜訪客戶：H11 > H2 > H8 > H14 > H5 >

總結(jié)

以上是生活随笔為你收集整理的基于经纬度和工作日的拜访轨迹问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。