一、题目
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;
}
咨询信息学课程或加信息学群请扫二维码加微信