搜狗第三题,吃糖

双端队列做的,感觉写的很一般,有大佬分享一下写的么?
#include<iostream>
#include<deque>
using namespace std;
int func(int* a, int length)
{
deque<int> s;
int max = 0;
for (int i = 1; i < length; i++)
{
if (a[i] > a[max])
max = i;
}
for (int i = 0; i <= max; i++)
s.push_back(a[i]);
for (int j = length - 1; j > max; j--)
s.push_front(a[j]);
int sum1 = 0;
int sum2 = 0;
while (!s.empty())
{

int num1 = s[0];
int num2 = s[length - 1];
if (num1 > num2)
{
sum1 = sum1 + num1;
s.pop_front();
}
else
{
sum1 = sum1 + num2;
s.pop_back();
}
length = s.size();
if (length > 0)
{
int num3 = s[0];
int num4 = s[length - 1];
if (num3 > num4)
{
sum2 = sum2 + num3;
s.pop_front();
}
else
{
sum2 = sum2 + num4;
s.pop_back();
}
}
length = s.size();
}
return (sum1 - sum2);
}
int main()
{
int N;
cin >> N;
int numbers[100];
int num;
for (int i = 0; i < N; i++)
{
cin >> numbers[i];
}
int res = func(numbers, N);
cout << res << endl;
system("pause");
return 0;
}

#搜狗##笔试题目#
全部评论
题目要求小明要先拿,所以最大的那个肯定是小明拿走了,为什么你存入deque的时候,还要把整个数组存入?第一个 if 条件还要比较队首和队尾,从最大值那里切开,队尾肯定是最大的啊。我思路跟你的一样,但是只能AC 40。
点赞 回复 分享
发布于 2018-09-15 20:57
我TM居然没想到双端队列,一直计算队列的对首对尾还记录是否被吃过。浪费了我很多时间
点赞 回复 分享
发布于 2018-09-15 08:26
dp[i][j] 代表区间[i, j]先手最多比后手多多少糖 dp[i][j] = max(num[i] - dp[i + 1][j], num[j] - dp[i][j - 1]);  大概是这样
点赞 回复 分享
发布于 2018-09-15 08:00
说下思路呗,过了多少啊
点赞 回复 分享
发布于 2018-09-15 01:02
点个赞
点赞 回复 分享
发布于 2018-09-14 23:40

相关推荐

07-07 14:30
复旦大学 Java
遇到这种人我也不知道说啥了
无能的丈夫:但我觉得这个hr语气没什么问题啊(没有恶意
点赞 评论 收藏
分享
nus2201602...:兄弟,你这个简历撕了丢了吧,就是一坨,去找几个项目,理解项目流程,看几遍就是你的了,看看八股就去干了,多看看牛客里别人发出来的简历,对着写,你这写的啥啊,纯一坨
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务