被美团挂的第二天早上神志不清,第三题写错了距离计算函数,人麻了
第一题
将数组划分成两个区间,要求区间和乘积最小。
经典的前缀和+枚举即完成
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int h[N];
int main() {
int n;
cin >> n;
memset(h, 0, sizeof(h));
long long sum = 0;
for (int i = 1; i <= n; i++) {
cin >> h[i];
sum += h[i];
h[i] += h[i - 1];
}
long long res = 1e18;
for (int i = 1; i < n; i++) {
res = min(res, h[i]* (sum - h[i]));
}
cout << res;
return 0;
}
// 64 位输出请用 printf("%lld")
第二题
给出长度为26的字符串给所有的字母定优先级,根据优先级对后续n个字符串从小到大进行排序。
字符串的前缀会比当前字符串更小。
直接采用自定义的比较函数进行排序。
不知道为什么该算法出现数组越界,只过70%
#include<bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
unordered_map<char, int>mp;
for (int i = 0; i < 26; i++) {
mp[s[i]] = i;
}
int n;
cin >> n;
vector<string> nums;
for (int i = 0; i < n; i++) {
string tmp;
cin >> tmp;
nums.push_back(tmp);
}
auto cmp = [&](string a, string b) {
int pox = 0;
int an = a.length();
int bn = b.length();
if (an == 0 || bn == 0) {
return an == 0 ? true:false;
}
while(pox < an && pox < bn && a[pox] == b[pox]) {
pox++;
}
if (pox == an) {
return true;
}
if (pox == bn) {
return false;
}
return mp[a[pox]] < mp[b[pox]];
};
sort(nums.begin(), nums.end(), cmp);
for (int i = 0; i < n; i++) {
cout << nums[i] << endl;
}
return 0;
}
第三题
所有的点都以1m/s的速度往其余点扩张,请问所有点连同起来的最少时间是多少。
可以直接使用最小生成树的Kruskal算法生成最小生成树,找到最长的边除2即可。
具体实现是将所有边纳入到优先队列中,每次弹出最小边,如果有一端还没被标记即加入到最小生成树中,对应的时间复杂度为\(O(n^2)\)
笔试中cacu的平方和写成了平方差,过0%,但思路应该没问题
#include <bits/stdc++.h>
using namespace std;
int pos[1005][2];
int h[1005];
double cacu(int pox1, int pox2) {
return sqrt(abs((double)(pos[pox1][0] - pos[pox2][0]) * (pos[pox1][0] - pos[pox2][0])
+ (double)(pos[pox1][1] - pos[pox2][1]) * (pos[pox1][1] - pos[pox2][1])));
}
struct node{
int x, y;
node(int a, int b){
x =a;
y = b;
}
bool operator<(const node& v) const {
return cacu(x, y) > cacu(v.x, v.y);
}
};
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> pos[i][0];
cin >> pos[i][1];
h[i] = 0;
}
double res = 0;
priority_queue<node>pq;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++){
pq.push(node(i, j));
}
}
while (!pq.empty()) {
node k = pq.top();
if (h[k.x] == 0 || h[k.y] == 0) {
res = max(res, cacu(k.x, k.y));
h[k.x] = 1;
h[k.y] = 1;
}
pq.pop();
}
int ans = round(res / 2);
if (res / 2 > ans) {
ans += 1;
}
cout << ans;
}
// 64 位输出请用 printf("%lld")
标签:pox,int,res,9.14,笔试,pos,cin,++,京东
From: https://www.cnblogs.com/tanch25/p/18414420