三星半导体研究院（SSIR软件）实习生/FTE

有N个钓鱼点和3个大门。每个大门都有一些渔民等待着到达最近的无人捕鱼地点。（渔民总数<=N）连续点之间的距离=闸门和最近点之间的距离=1 m 一次只能打开一个门，在打开下一个门之前，该门的所有渔民必须占据这些位置。距离的计算方法是：门到最近的点+最近的点到最近的空位。求出所有渔民需要行走的最小距离的总和。需要采取的投入：捕鱼点的数量大门的位置每个大门的渔民人数

null

遵循以下示例：

test case

捕鱼点总数=10 5名渔民在4号位置的1号门处， 2名渔民在位于6号位置的2号门处， 2名渔民在位于位置10的3号门处， 如果闸门按G1->G2->G3顺序打开

安排如下：

Case 1

距离的计算方法是：门到最近的点+最近的点到最近的空位。 G1门打开后，渔民被安置在标有1的位置。距离=11米 G2门打开后，渔民被安置在标有2的位置。距离=5米 G3闸门打开后，渔民被安置在标有3的位置。距离=3米按此顺序排列的总距离：11+5+3=19

如果闸门按G2->G1->G3的顺序打开 案例1 -2号门的最后一名渔民被安置在7号位置最终安排如下：

Case 2B

G2门打开后，渔民被安置在标有2的位置。距离=3米 G1门打开后，渔民被安置在标有1的位置。距离=12米 G3闸门打开后，渔民被安置在标有3的位置。距离=3米按此顺序排列的总距离：3+12+3=18

案例2 -2号门的最后一名渔民被安置在5号位置最终安排如下：

Case

G2门打开后，渔民被安置在标有2的位置。距离=3米 G1门打开后，渔民被安置在标有1的位置。距离=14米 G3闸门打开后，渔民被安置在标有3的位置。距离=3米按此顺序排列的总距离：3+14+3=20 其他情况是多余的所以最小距离是18 解决方案：

生成所有组合，并在所有闸门组合中指定渔民，以计算最小步行距离。生成组合可以采用递归和迭代两种方式。现在，为了消除不必要的排列，我们可以得出结论，为了达到最小的步行距离，来自特定大门的渔民必须呆在一起，即他们应该占据连续的捕鱼点。因此，我们可以将问题想象为3个区块（渔民组）在整个捕鱼范围内滑动。答案是最低限度的。

C++

                         #define _CRT_SECURE_NO_WARNINGS                       
                         #include<iostream>                       
                         using                                     namespace                                     std;                       
                         #define MAX 3                       
           
                         int                                     fishspot[100];                                     // fishing spots                       
                         int                                     gate[MAX];                                     // position of gates                       
                         int                                     fishermen[MAX];                                     // no of fishermen at each gate                       
                         int                                     N;                                     // total no of fishing spots                       
                         int                                     visited[MAX];                                     // occupied fishing spots                       
                         int                                     Answer;                                     // result                       
           
                         // To unmark spots occupied by fishermen of gate# index                       
                         class                                     GFG                       
                         {                       
                         public                                     :                       
                         void                                     reset_fishspot(                                     int                                     index)                       
                         {                       
                                                 int                                     i;                       
                                                 for                                     (i = 1; i <= N; i++)                       
                                                 if                                     (fishspot[i] == index + 1)                       
                                                 fishspot[i] = 0;                       
                         }                       
           
                         // Calculate minimum distance while                       
                         // allotting spots to fishermen of gate# index.                       
                         // Returns number of positions possible                       
                         // with minimum distance.                       
                         // pos1, pos2 is used to return positions                       
                         int                                     calculate_distance(                                     int                                     index,                                     int                                     *pos1,                       
                                                 int                                     *pos2,                                     int                                     *score)                       
                         {                       
                                                 int                                     i, sum = 0, left_min = 999999,                       
                                                 right_min = 999999,                       
                                                 left, right, npos = 0;                       
                                                 *pos1 = *pos2 = *score = 0;                       
           
                                                 left = right = gate[index];                       
           
                                                 // Allot spots to all fishermen except                       
                                                 // last based on minimum distance                       
                                                 for                                     (i = 1; i < fishermen[index]; i++)                       
                                                 {                       
                                                 if                                     (fishspot[gate[index]] == 0)                       
                                                 {                       
                                                 sum++;                       
                                                 fishspot[gate[index]] = index + 1;                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 left_min = right_min = 999999;                       
           
                                                 while                                     ((left > 0) && (fishspot[left] > 0))                       
                                                 left--;                       
           
                                                 while                                     ((right <= N) &&                       
                                                 (fishspot[right] > 0))                       
                                                 right++;                       
           
                                                 if                                     ((left > 0) && (fishspot[left] == 0))                       
                                                 left_min = gate[index] - left + 1;                       
           
                                                 if                                     ((right <= N) && (fishspot[right] == 0))                       
                                                 right_min = right - gate[index] + 1;                       
           
                                                 if                                     (right_min == left_min)                       
                                                 {                       
                                                 // Place 2 fishermen, if available                       
                                                 if                                     ((fishermen[index] - i - 1) > 1)                       
                                                 {                       
                                                 fishspot[left] = fishspot[right] = index + 1;                       
                                                 sum += (2 * left_min);                       
                                                 i++;                       
           
                                                 // If all fishermen are alloted spots                       
                                                 if                                     (i == fishermen[index])                       
                                                 {                       
                                                 npos = 1;                       
                                                 *score = sum;                       
                                                 return                                     npos;                       
                                                 }                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 sum += left_min;                       
                                                 fishspot[left] = index + 1;                       
                                                 }                       
                                                 }                       
                                                 else                                     if                                     (left_min < right_min)                       
                                                 {                       
                                                 sum += left_min;                       
                                                 fishspot[left] = index + 1;                       
                                                 }                       
                                                 else                                     if                                     (right_min < left_min)                       
                                                 {                       
                                                 sum += right_min;                       
                                                 fishspot[right] = index + 1;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 left_min = right_min = 99999;                       
           
                                                 // Allot spot to last fishermen                       
                                                 while                                     ((left > 0) && (fishspot[left] > 0))                       
                                                 left--;                       
           
                                                 if                                     ((left > 0) && (fishspot[left] == 0))                       
                                                 left_min = gate[index] - left + 1;                       
           
                                                 while                                     ((right <= N) && (fishspot[right] > 0))                       
                                                 right++;                       
           
                                                 if                                     ((right <= N) && (fishspot[right] == 0))                       
                                                 right_min = right - gate[index] + 1;                       
           
                                                 if                                     ((sum + left_min) == (sum + right_min))                       
                                                 {                       
                                                 npos = 2;                       
                                                 *pos1 = left;                       
                                                 *pos2 = right;                       
                                                 *score = sum + left_min;                       
                                                 }                       
                                                 else                                     if                                     ((sum + left_min) >                       
                                                 (sum + right_min))                       
                                                 {                       
                                                 npos = 1;                       
                                                 *score = sum + right_min;                       
                                                 fishspot[right] = index + 1;                       
                                                 }                       
                                                 else                                     if                                     ((sum + left_min) <                       
                                                 (sum + right_min))                       
                                                 {                       
                                                 npos = 1;                       
                                                 *score = sum + left_min;                       
                                                 fishspot[left] = index + 1;                       
                                                 }                       
                                                 return                                     npos;                       
                         }                       
           
                         // Solve is used to select next gate                       
                         // and generate all combinations.                       
                         void                                     solve(                                     int                                     index,                                     int                                     sum,                                     int                                     count)                       
                         {                       
                                                 int                                     npos, pos1, pos2, score, i;                       
           
                                                 visited[index] = 1;                       
           
                                                 if                                     (sum > Answer)                       
                                                 return                                     ;                       
           
                                                 npos = calculate_distance(index, &pos1,                       
                                                 &pos2, &score);                       
                                                 sum += score;                       
           
                                                 if                                     (count == MAX)                       
                                                 {                       
                                                 if                                     (Answer > sum)                       
                                                 Answer = sum;                       
           
                                                 return                                     ;                       
                                                 }                       
           
                                                 if                                     (npos == 1)                       
                                                 {                       
                                                 for                                     (i = 0; i < MAX; i++)                       
                                                 {                       
                                                 if                                     (visited[i] == 0)                       
                                                 {                       
                                                 solve(i, sum, count + 1);                       
                                                 visited[i] = 0;                       
                                                 reset_fishspot(i);                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 else                                     if                                     (npos == 2)                       
                                                 {                       
                                                 fishspot[pos1] = index + 1;                       
                                                 for                                     (i = 0; i < MAX; i++)                       
                                                 {                       
                                                 if                                     (visited[i] == 0)                       
                                                 {                       
                                                 solve(i, sum, count + 1);                       
                                                 visited[i] = 0;                       
                                                 reset_fishspot(i);                       
                                                 }                       
                                                 }                       
           
                                                 fishspot[pos1] = 0;                       
                                                 fishspot[pos2] = index + 1;                       
                                                 for                                     (i = 0; i < MAX; i++)                       
                                                 {                       
                                                 if                                     (visited[i] == 0)                       
                                                 {                       
                                                 solve(i, sum, count + 1);                       
                                                 visited[i] = 0;                       
                                                 reset_fishspot(i);                       
                                                 }                       
                                                 }                       
                                                 fishspot[pos2] = 0;                       
                                                 }                       
                         }                       
                         };                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 GFG g;                       
           
                                                 int                                     i;                       
                                                 /*scanf("%d", &N); // for input                       
                                   
                                                 for (i = 0; i < MAX; i++)                       
                                                 {                       
                                                 scanf("%d %d", &gate[i], &fishermen[i]);                       
                                                 visited[i] = 0;                       
                                                 }*/                       
                                   
                                                 N = 10;                                     // total no of fishing spots                       
                                   
                                                 // position of gates(1-based indexing)                       
                                                 gate[0] = 4;                       
                                                 gate[1] = 6;                       
                                                 gate[2] = 10;                       
                                   
                                                 //no of fishermen at each gate                       
                                                 fishermen[0] = 5;                                     //gate1                       
                                                 fishermen[1] = 2;                                     //gate 2                       
                                                 fishermen[2] = 2;                                     //gate 3                       
           
                                                 for                                     (i = 1; i <= N; i++)                       
                                                 fishspot[i] = 0;                       
           
                                                 Answer = 999999;                       
           
                                                 for                                     (i = 0; i < MAX; i++)                       
                                                 {                       
                                                 g.solve(i, 0, 1);                       
                                                 visited[i] = 0;                       
                                                 g.reset_fishspot(i);                       
                                                 }                       
           
                                                 cout << Answer << endl;                       
           
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by SoM15242                       

C

                         #define _CRT_SECURE_NO_WARNINGS                       
                         #include<stdio.h>                       
           
                         #define MAX 3                       
           
                         int                                     fishspot[100];                                     // fishing spots                       
                         int                                     gate[MAX];                                     // position of gates                       
                         int                                     fishermen[MAX];                                     // no of fishermen at each gate                       
                         int                                     N;                                     // total no of fishing spots                       
                         int                                     visited[MAX];                                     // occupied fishing spots                       
                         int                                     Answer;                                     // result                       
           
                         //To unmark spots occupied by fishermen of gate# index                       
                         void                                     reset_fishspot(                                     int                                     index)                       
                         {                       
                                                 int                                     i;                       
                                                 for                                     (i = 1; i <= N; i++)                       
                                                 if                                     (fishspot[i] == index + 1)                       
                                                 fishspot[i] = 0;                       
                         }                       
           
                         // Calculate minimum distance while allotting spots to                       
                         // fishermen of gate# index.                       
                         // Returns number of positions possible with minimum distance.                       
                         // pos1, pos2 is used to return positions                       
                         int                                     calculate_distance(                                     int                                     index,                                     int                                     *pos1,                                     int                                     *pos2,                                     int                                     *score)                       
                         {                       
                                                 int                                     i, sum = 0, left_min = 999999, right_min = 999999,                       
                                                 left, right, npos = 0;                       
                                                 *pos1 = *pos2 = *score = 0;                       
           
                                                 left = right = gate[index];                       
           
                                                 // Allot spots to all fishermen except last based on                       
                                                 // minimum distance                       
                                                 for                                     (i = 1; i < fishermen[index]; i++)                       
                                                 {                       
                                                 if                                     (fishspot[gate[index]] == 0)                       
                                                 {                       
                                                 sum++;                       
                                                 fishspot[gate[index]] = index + 1;                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 left_min = right_min = 999999;                       
           
                                                 while                                     ((left > 0) && (fishspot[left] > 0))                       
                                                 left--;                       
           
                                                 while                                     ((right <= N) && (fishspot[right] > 0))                       
                                                 right++;                       
           
                                                 if                                     ((left > 0) && (fishspot[left] == 0))                       
                                                 left_min = gate[index] - left + 1;                       
           
                                                 if                                     ((right <= N) && (fishspot[right] == 0))                       
                                                 right_min = right - gate[index] + 1;                       
           
                                                 if                                     (right_min == left_min)                       
                                                 {                       
                                                 // Place 2 fishermen, if available                       
                                                 if                                     ((fishermen[index] - i - 1) > 1)                       
                                                 {                       
                                                 fishspot[left] = fishspot[right] = index + 1;                       
                                                 sum += (2 * left_min);                       
                                                 i++;                       
           
                                                 // If all fishermen are alloted spots                       
                                                 if                                     (i == fishermen[index])                       
                                                 {                       
                                                 npos = 1;                       
                                                 *score = sum;                       
                                                 return                                     npos;                       
                                                 }                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 sum += left_min;                       
                                                 fishspot[left] = index + 1;                       
                                                 }                       
                                                 }                       
                                                 else                                     if                                     (left_min < right_min)                       
                                                 {                       
                                                 sum += left_min;                       
                                                 fishspot[left] = index + 1;                       
                                                 }                       
                                                 else                                     if                                     (right_min < left_min)                       
                                                 {                       
                                                 sum += right_min;                       
                                                 fishspot[right] = index + 1;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 left_min = right_min = 99999;                       
           
                                                 // Allot spot to last fishermen                       
                                                 while                                     ((left > 0) && (fishspot[left] > 0))                       
                                                 left--;                       
           
                                                 if                                     ((left > 0) && (fishspot[left] == 0))                       
                                                 left_min = gate[index] - left + 1;                       
           
                                                 while                                     ((right <= N) && (fishspot[right] > 0))                       
                                                 right++;                       
           
                                                 if                                     ((right <= N) && (fishspot[right] == 0))                       
                                                 right_min = right - gate[index] + 1;                       
           
                                                 if                                     ((sum + left_min) == (sum + right_min))                       
                                                 {                       
                                                 npos = 2;                       
                                                 *pos1 = left;                       
                                                 *pos2 = right;                       
                                                 *score = sum + left_min;                       
                                                 }                       
                                                 else                                     if                                     ((sum + left_min) > (sum + right_min))                       
                                                 {                       
                                                 npos = 1;                       
                                                 *score = sum + right_min;                       
                                                 fishspot[right] = index + 1;                       
                                                 }                       
                                                 else                                     if                                     ((sum + left_min) < (sum + right_min))                       
                                                 {                       
                                                 npos = 1;                       
                                                 *score = sum + left_min;                       
                                                 fishspot[left] = index + 1;                       
                                                 }                       
           
                                                 return                                     npos;                       
                         }                       
           
                         // Solve is used to select next gate and generate all combinations.                       
                         void                                     solve(                                     int                                     index,                                     int                                     sum,                                     int                                     count)                       
                         {                       
                                                 int                                     npos, pos1, pos2, score, i;                       
           
                                                 visited[index] = 1;                       
           
                                                 if                                     (sum > Answer)                       
                                                 return                                     ;                       
           
                                                 npos = calculate_distance(index, &pos1, &pos2, &score);                       
                                                 sum += score;                       
           
                                                 if                                     (count == MAX)                       
                                                 {                       
                                                 if                                     (Answer > sum)                       
                                                 Answer = sum;                       
           
                                                 return                                     ;                       
                                                 }                       
           
                                                 if                                     (npos == 1)                       
                                                 {                       
                                                 for                                     (i = 0; i < MAX; i++)                       
                                                 {                       
                                                 if                                     (visited[i] == 0)                       
                                                 {                       
                                                 solve(i, sum, count + 1);                       
                                                 visited[i] = 0;                       
                                                 reset_fishspot(i);                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 else                                     if                                     (npos == 2)                       
                                                 {                       
                                                 fishspot[pos1] = index + 1;                       
                                                 for                                     (i = 0; i < MAX; i++)                       
                                                 {                       
                                                 if                                     (visited[i] == 0)                       
                                                 {                       
                                                 solve(i, sum, count + 1);                       
                                                 visited[i] = 0;                       
                                                 reset_fishspot(i);                       
                                                 }                       
                                                 }                       
           
                                                 fishspot[pos1] = 0;                       
                                                 fishspot[pos2] = index + 1;                       
                                                 for                                     (i = 0; i < MAX; i++)                       
                                                 {                       
                                                 if                                     (visited[i] == 0)                       
                                                 {                       
                                                 solve(i, sum, count + 1);                       
                                                 visited[i] = 0;                       
                                                 reset_fishspot(i);                       
                                                 }                       
                                                 }                       
                                                 fishspot[pos2] = 0;                       
                                                 }                       
                         }                       
           
                         int                                     main()                                     // driver function                       
                         {                       
           
                                                 int                                     i;                       
                                                 /*scanf("%d", &N); // for input                       
                                   
                                                 for (i = 0; i < MAX; i++)                       
                                                 {                       
                                                 scanf("%d %d", &gate[i], &fishermen[i]);                       
                                                 visited[i] = 0;                       
                                                 }*/                       
                                   
                                                 N=10;                                     // total no of fishing spots                       
                                   
                                                 //position of gates(1-based indexing)                       
                                                 gate[0]=4;                       
                                                 gate[1]=6;                       
                                                 gate[2]=10;                       
                                   
                                                 //no of fishermen at each gate                       
                                                 fishermen[0]=5;                                     //gate1                       
                                                 fishermen[1]=2;                                     //gate 2                       
                                                 fishermen[2]=2;                                     //gate 3                       
                                   
                                   
           
                                                 for                                     (i = 1; i <= N; i++)                       
                                                 fishspot[i] = 0;                       
           
                                                 Answer = 999999;                       
           
                                                 for                                     (i = 0; i < MAX; i++)                       
                                                 {                       
                                                 solve(i, 0, 1);                       
                                                 visited[i] = 0;                       
                                                 reset_fishspot(i);                       
                                                 }                       
           
                                                 printf                                     (                                     "%d"                                     , Answer);                       
                                   
                                                 return                                     0;                       
                         }                       

输出：

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章

三星半导体研究院（SSIR软件）实习生/FTE | Set-1

C++

C