2022 年 3 月 1 日开课啦!
报名链接:https://www.icourse163.org/learn/ZJU-93001?tid=1466830443
常用软件下载
https://bytodance.feishu.cn/docs/doccn7ZRXBvN8HMEfF8LNq9gKig
备用下载地址
https://pan.mhatp.cn/%E8%BD%AF%E4%BB%B6
01-复杂度3 二分查找 (20 分)
复习一下二分查找模版
Position BinarySearch( List L, ElementType X )
{
int l=1,r=L->Last;
while(l < r)
{
int mid = l + r >> 1;
if(L->Data[mid] >= X){
r = mid;
}else{
l = mid + 1;
}
}
if(L->Data[r] == X){
return r;
}else{
return NotFound;
}
}
01-复杂度1 最大子列和问题 (20 分)
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
// typedef long long ll;
// 后来发现 int 也能过
using namespace std;
const int N = 1e5 + 10;
int n;
int arr[N];
int thissum = 0, maxsum = -0x3f3f3f;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
for (int i = 0; i < n; i++) {
thissum += arr[i];
if (thissum < 0) thissum = 0;
maxsum = max(maxsum, thissum);
}
printf("%d", maxsum);
return 0;
}
01-复杂度2 Maximum Subsequence Sum (25 分)
不知道哪错了,呜呜
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
int n;
int arr[N];
int thissum = 0, maxsum = -0x3f3f3f;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
int maxl, maxr;
bool first = true;
int thisl,thisr;
for (int i = 0; i < n; i++) {
thissum += arr[i];
if(first){
thisl = i;
thisr = i;
first = false;
}else{
thisr = i;
}
if (thissum < 0) {
// 重新开始一个
thissum = 0;
first = true;
}
if (thissum > maxsum) {
maxsum = thissum;
maxl = thisl;
maxr = thisr;
}
}
printf("%d %d %d\n", maxsum, maxl, maxr);
return 0;
}
测试视频,请忽视