链接：https://www.nowcoder.com/acm/contest/140/D
来源：牛客网
The first line contains an integer T(0<T<=5), denoting the number of test cases.
In each test case, there is one integer n(0<n<=100000) in the first line,denoting the number of stores.
For the next line, There are n integers in range [0,2147483648), denoting a[1..n].
For each test case, print a single line containing 2 integers, denoting the maximum profit and the minimum number of transactions.示例1
3 4
分析：我每次只能每一个，然后必须卖掉才能买下一个，中间的利润要最大，交易次数最小
我们可以在坐标系里标出每个点，横坐标点的位置，纵坐标点的值
然后我们发现我们所要求得就是每条非递减线段的值
如下图中，我们要求的就是AB+DE
注意点值相同的时候要加上这条非递减数列的最后的值，如果不判相等中间断了结果就错了
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define debug(a) cout << #a << " " << a << endl
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 10000007;
typedef long long ll;
int t,n;
ll a[maxn],ans,s;
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>t;
while(t--){
ans=s=0;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
if(n<2) {
cout<<"0 0"<<endl;
continue;
}
int fg=0;
for(int i=2;i<=n;i++) {
if(a[i]==a[i-1]) continue;
if(a[i]>=a[i-1]) ans+=(a[i]-a[i-1]),fg=1;
else if(fg) s+=2,fg=0;
}
if(a[n]>=a[n-1]&&fg) s+=2;
cout<<ans<<" "<<s<<endl;
}
return 0;
}
|
参赛类别 |
作品名称 |
作品负责人信息 |
指导老师 |
备注 |
||
|
姓 名 |
年级及专业 |
联系电话 |
||||
|
“互联网+”信息技术服务 |
乐客校园直播 |
刘杰 |
软件工程 |
15274451321 |
黄伟 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
原文：https://www.cnblogs.com/l609929321/p/9347363.html