ios网站开发教程,seo是指什么职位,广州百度网站快速排名,网校网站建设多少钱太戈编程736题
题目描述#xff1a;
你是一只汪星人#xff0c;地球毁灭后你回到了汪星#xff0c;这里每天有n个小时#xff0c;你需要为自己选择正好连续的m小时作为每天睡眠的时间。从凌晨开始#xff0c;第i小时内的睡眠质量为xi#xff0c;请问经过选择后#xf…太戈编程736题
题目描述
你是一只汪星人地球毁灭后你回到了汪星这里每天有n个小时你需要为自己选择正好连续的m小时作为每天睡眠的时间。从凌晨开始第i小时内的睡眠质量为xi请问经过选择后你的睡眠质量总和最大是多少
法1 断环拉直克隆
图示 首先这道题不是一般的前缀和问题因为尾指针可以指向首指针。这个方法是普通方法先拉直再把数组复制一遍所以数组至少要开两倍然后算前缀和最后扫一遍m1到2*n算差分最大值。写代码八
cinnm;
for(int i1;in;i) cinx[i];
for(int in1;in*2;i) x[i]x[i-n];
s[0]0;
for(int i1;in*2;i) s[i]s[i-1]x[i];
int anss[m];
for(int im1;in*2;i)ansmax(ans,s[i]-s[i-m]);
coutansendl;
法2 滑动窗口 #include bits/stdc.h
using namespace std;
int n,m;
int x[200009];
int cur,ans;
int main(){freopen(dog.in,r,stdin);freopen(dog.out,w,stdout);cinnm;for(int i1;in;i){cinx[i];x[in]x[i];}for(int i1;im;i) curx[i];anscur;for(int i2;in;i){int curcur-x[i-1]x[im-1];ansmax(cur,ans);}coutansendl;return 0;
}
就是一个滑动窗口看起来比法1简洁
法3 首位情况分类
图示 那么先正常前缀和再m-1次特判。
cinnm;
for(int i1;in;i) cinx[i];
for(int i1;in;i) s[i]s[i-1]x[i];
int anss[m];
for(int im1;in;i)ansmax(ans,s[i]-s[i-m]);
for(int i1;im-1;i)ansmax(ans,s[i]s[n]-s[n-mi]);
coutansendl;
法4 循环单链表数据结构
因为这一个数据结构我没讲过所以……我来给大家梳理一遍代码。先来看普通单链表八
结构体指针-CSDN博客
节点函数
typedef struct _node
{int data;struct _node *next;
}node;
创造链表
struct node *create(int n)
{node *head;node *tail;node *h;headtail(node*)(malloc)(sizeof(node));hhead;node *p;int in;int d0;coutPlease input the intergers.endl;for(in;i0;i--){p(node*)(malloc)(size(node));cind;p-datad;p-nextNULL;tail-nextp;tailp;}tail-nexth;return h;
} 链表查找函数
struct node *search(node *head,node *s,int x){int y;while(s!head){ys-data;if(xy) return s;else ss-next;}
}
常见使用
int main(){int n;cinn;node *prt;prtcreate(n);node *first;firstprt-next;node *pr;prfirst;while(first!prt){coutfirst-data ;firstfirst-next;}int number;node *num;coutendl;cinnumber;numsearch(prt,pr,number);coutnum-data;return 0;
} 嗯……这个方法自己尝试八比较有风险但是如果用对了就很酷。
太戈编程650题
题目描述
你作为校长正在筹办校园开放日希望邀请学生和家长来参观期间有n个公开课在不同教室开展。第i个公开课从时刻si分钟到时刻ti分钟需要摆放xi把椅子。椅子从一个教室搬到另一个教室需要5分钟假设人手足够多不管搬几把椅子都是这个时间。请问至少需要几把椅子
这题用差分真的真的很好做
差分的话想到有些小朋友还不懂我来讲一下吧。差分有什么用呢差分可以使一个数组S中一段区间每个元素加上常数C。比如说有任意一个数组S区间[l,r]内每一个元素均加上常数j。若用暴力枚举[l,r]中每一个元素加j时间复杂度为O(n)显然有更快的算法。若用差分假设S的差分数组为A则在A中标记第l个加j第r1个减j这时再把差分数组化成前缀和数组即可得到目标数组时间复杂度O(1)
所以……上代码八
cinn;
for(int i1;in;i){cinabx;d[a]x;d[b5]-x;
}
for(int i1;iR;i) s[i]s[i-1]d[i];
cout*max_element(s1,s1n);
拓展太戈编程2667
数据分类
int main(){freopen(training.in,r,stdin);freopen(training.out,w,stdout);input();if(n1000m1000) solveBF();else solve();return 0;
} BF
void solveBF(){for(l i1;im;i){ll l,r;cinlr;ll ans0;for(ll jl;jr;j) ansh[j]*(j-l1);coutans ;}
}
满分解法 数学不好的请退出……
void solve(){for(ll i1;in;i){s[i]s[i-1]h[i];g[i]g[i-1]h[i]*i;}for(ll i1;im;i){ll l,r;cinlr;ll ansg[r]-g[l-1]-(s[r]-s[l-1])*(l-1);coutans ;}
} 希望这些对大家有用三连必回。
