做搜索关键词任务网站,在线教育网站html模板,建设银行网站注册用户名,济南国画网站建设题目链接
分析
枚举每一个城市#xff0c;并计算以他做聚会地点的价钱#xff0c;取最小#xff0c;如果相同则取最靠后的#xff0c;时间复杂度为 Θ ( n 2 ) \Theta(n^2) Θ(n2)。
其实可以发现将城市 i i i 换到城市 i 1 i1 i1#xff0c;那么 i i i 之前的包括…题目链接
分析
枚举每一个城市并计算以他做聚会地点的价钱取最小如果相同则取最靠后的时间复杂度为 Θ ( n 2 ) \Theta(n^2) Θ(n2)。
其实可以发现将城市 i i i 换到城市 i 1 i1 i1那么 i i i 之前的包括 i i i 的所有人都要多走 i i i 到 i 1 i1 i1 之间的距离而 i 1 i1 i1 之后的所有人包括 i 1 i1 i1 就会少走 i i i 到 i 1 i1 i1 之间的距离所以我们可以枚举每个点在 Θ ( 1 ) \Theta(1) Θ(1) 算出以他做聚会地点的价钱时间复杂度为 Θ ( n ) \Theta(n) Θ(n)。
代码 Θ ( n ) \Theta(n) Θ(n) 代码
#include bits/stdc.h
#define int long longusing namespace std;const int N 10005;
int pre[N], erp[N];struct node{int stu, km;string name;
}a[N];signed main(){int n 0;while(~0){n ;cin a[n].stu a[n].km a[n].name;if(a[n].name Moscow){break;}}for(int i 1, j n; i n j 1; i , j --){pre[i] pre[i - 1] a[i].stu;//前缀和求出i号城市后包括i号城市的人数erp[j] erp[j 1] a[j].stu;//后缀和同理}int ans 0;string AnsName a[1].name;for(int i 2; i n; i ){//先预处理一遍求出所有城市到1号城市的距离ans (a[1].km - a[i].km) * a[i].stu;}for(int i 1; i n; i ){//把聚会地点从i号城市换到i1号城市int dist a[i].km - a[i 1].km;int money ans pre[i] * dist - erp[i 1] * dist;if(money ans){ans money;AnsName a[i 1].name;}}cout AnsName ans;return 0;
}
