美团笔试编程题-9.11

本文主要是介绍美团笔试编程题-9.11，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：一个商家选择地址x[i]，在该位置的价值为y[i]。问选择多个地址并且使得任意两个地址之差绝对值大于等于k。
输入：k，x，y
如：
2
1,3,2,5
4,5,1,1
输出：
1,3,5
10

一种较笨拙的思路是：
1.先对x从小到排序
2.两层循环寻找最大价值

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>using namespace std;int main()
{int k;string x, y;vector<vector<int> > xy(100, vector<int>(2,0));while (cin >> k >> x >> y){int lenx = x.size();int len = 0;for (int i=0; i<lenx; i++){if (i%2 == 0){//cout << "x[i]：" << x[i] << endl;xy[len][0] = x[i]-'0';xy[len][1] = y[i]-'0';len++;}}//二维数组按第一列从小到大排序for (int i=0; i<len; i++){for (int j=len-1; j>i; j--){if (xy[j][0] < xy[j-1][0]){int temp, temp1;temp = xy[j][0];xy[j][0] = xy[j-1][0];xy[j-1][0] = temp;temp1 = xy[j][1];xy[j][1] = xy[j-1][1];xy[j-1][1] = temp1;}}}int ans = 0, left = 0;for (int i=0; i<len; i++){int ans_temp = xy[i][1];int pos = i;for (int j=i+1; j<len; j++){if (xy[j][0] - xy[pos][0] >= k){ans_temp += xy[j][1];pos = j;}}if (ans_temp > ans){left = i;}ans = ans >= ans_temp ? ans:ans_temp;}cout << xy[left][0];int pos = left;for (int i=left+1; i<len; i++){if (xy[i][0] - xy[pos][0] >= k){cout << "," << xy[i][0];pos = i;}}cout << endl;cout << ans << endl;}return 0;
}

这篇关于美团笔试编程题-9.11的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---