二刷算法基础题DAY11

10.7号图论代码搞一搞，10.8号开始做做真题

货仓选址 题目链接

暴力超时 过了60%数据 贪心太难了，暂时放一放。就先学到这。

#include<iostream> #include<algorithm> #include<cmath> using namespace std; const int N=100000+10 ; int n; int l,r; int a[N]; int rr=0x7fffffff; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } sort(a+1,a+n+1); l=a[1]; r=a[n]; int index=1; for(int i=l;i<=r;i++){ int res=0; for(int j=1;j<=n;j++){ res+=abs(i-a[j]); if(res>rr){ res=rr; break; } } rr=res; } cout<<rr; return 0; }

第二版，感觉是优化了的，vs运行没问题，但是就是说我 Segmentation Fault 不让运行。

#include<iostream> #include<algorithm> #include<cmath> using namespace std; const int N=100000+10 ; int n; int l,r; int a[N]; int rr=0x7fffffff; int index=1; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; l=min(l,a[i]); r=max(r,a[i]); } int i=l; while(i<=r){ int res=0; for(int j=1;j<=n;j++){ res+=abs(i-a[j]); if(res>rr){ res=rr; break; } } rr=res; ++index; i=a[index]; } cout<<rr<<endl; return 0; }