题目描述
求解最短送货路程
主要是应用绝对值不等式得出中间是最优点
样例
blablabla
算法1
(快排与绝对值不等式) $O(nlogn)$
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
int N,store[100010];
int main()
{
cin>>N;
for(int i=1;i<=N;i)
{
cin>>store[i];
}
sort(store+1,store+N+1);
int res=0;
for(int i=1;i<=N;i)res+=abs(store[i]-store[N/2+1]);
cout<<res;
return 0;
}
算法二:
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
int N,store[100010];
int main()
{
cin>>N;
for(int i=1;i<=N;i)
{
cin>>store[i];
}
sort(store+1,store+N+1);
int res=0;
for(int i=1;i<=N;i)res+=abs(store[i]-store[i/2+1]);
cout<<res;
return 0;
}
算法3:主要运用了nth_element(起始,中间,末尾) (n)
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
int N,store[100010];
int main()
{
cin>>N;
for(int i=1;i<=N;i)
{
cin>>store[i];
}
nth_element(store+1,store+N/2+1,store+N+1);
int res=0;
for(int i=1;i<=N;i)res+=abs(store[i]-store[N/2+1]);
cout<<res;
return 0;
}
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
?
怎么了???
有什么疑问么?