《啤酒厂选址》题解报告

ゝ一世哀愁。 2022-10-29 03:24 136阅读 0赞

# 一、题目 #

http://noi.openjudge.cn/ch0113/19/  
https://www.luogu.com.cn/problem/T166959

# 二、思路 #

对于第i个点作为出发点，到第j点的时间，判断i到j的距离是否小于环岛总长度的一半。若小于一半，顺时针路线送啤酒，若大于一半，逆时针路线送啤酒；若等于一半，顺时针逆时针都无所谓。

# 三、代码 #

#include <bits/stdc++.h>
    using namespace std;
    const int maxN = 10010;
    int need[maxN], dist[maxN];//分别为结点所需与跟下一节点的距离
    
    int main()
    { 
        freopen("test.in", "r", stdin);
    
        int minCost=INT_MAX, flag=0, length=0;
        int n;
        cin>>n;
    
        for (int i = 0; i < n; ++i)
        { 
            cin>>need[i]>>dist[i];
            length+=dist[i]; 环的总长度
        }
    
        for (int i = 0; i < n; ++i)
        { 
            int cost=0, len=0;//len为第i个点到第j个点的距离
            int pos=0;
            for (int j = i; j < n + i; ++j) //不能写成j < n;因为是环状
            { 
                pos=(j>=n)?j-n:j;
    
                if(len<length/2)
                { 
                    cost+=len*need[pos];
                }
                else
                { 
                    cost+=(length-len)*need[pos];
                }
                len+=dist[pos];  //len写在最后面，可以与dist错开一位
            }
    
            if(cost<minCost)
            { 
                //得所求
                minCost=cost;
                flag=i;
            }
        }
    
        cout<<flag<<","<<minCost;
    
        return 0;
    }

> 咨询信息学课程或加信息学群请扫二维码加微信  
> ![在这里插入图片描述][20210208105104740.png]

[20210208105104740.png]: /images/20221024/707eb99fe9fa454097aec2c7d7cddbf2.png