携程实习笔试3-4
第一题，给算式求值，算式有三种，（+ a b c）返回a+b+c的值，(- a b c d)返回a-b-c-d的值，（* a b )返回a * b的值，然后各种嵌套这几个算式。
示例输入
（+ 3 4）
（- 9 4 5）
（- （* 4 5） 4 5）
（* （+ 2 3）（- 100 （+ 20 10）））
输出
7
0
11
350
写了半天把自己绕晕了，结束后改出来一个版本，也没法测试了，样例倒是过了。
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int main()
{
string ss;
while (getline(cin, ss)){
int n = ss.size();
stack<char> stac;
stack<int> num;
for (int i = 0; i < n; ++i){
char c = ss[i];
if (c == ' ') continue;
else if (c == '(') num.push(-1);
else if (c == '+' || c == '-' || c == '*') stac.push(c);
else if (c == ')'){
if (stac.top() == '+'){
int tmp = 0;
while (num.top() != -1){
tmp += num.top();
num.pop();
}
num.pop();
num.push(tmp);
}
else if (stac.top() == '-'){
int tmp = 0;
int pre;
while (num.top() != -1){
tmp += num.top();
pre = num.top();
num.pop();
}
num.pop();
num.push(2*pre-tmp);
}
else{
int tmp = 1;
while (num.top() != -1){
tmp *= num.top();
num.pop();
}
num.pop();
num.push(tmp);
}
stac.pop();
}
else if ( ss[i]>='0' && ss[i]<='9'){
int tmp = 0;
while (i < n && ss[i]>='0' && ss[i]<='9'){
tmp = (ss[i]-'0') + tmp*10;
i++;
}
--i;
num.push(tmp);
}
}
cout << num.top() << endl;
}
return 0;
} 第二题发红包，给一个序列的红包，请你分割成n+1份(每份要连续)，使得其中钱最少的那一份尽可能多。例题序列为[1,2,3,4,5,6,7,8,9]，分割成6份，答案是6。
[1,2,3],[4,5],[6],[7],[8],[9]
我赶脚就是二分这个结果，贪心看看按照这个结果能不能分出n+1份及以上，不能就右边界往左，能就左边界往右，然而0%...
int m = packets.size();
int right = 0;
for (int i = 0; i < m; ++i) right += packets[i];
int left = 0;
while (left < right){
int mid = left + (right - left) / 2;
int cnt = 0;
int sum = 0;
for (int i = 0; i < m; ++i){
sum += packets[i];
if (sum >= mid){
cnt++;
sum = 0;
}
}
if (cnt >= n+1) left = mid;
else right = mid - 1;
}
return left; 有大佬可以帮忙看看吗
美团公司氛围 1756人发布