Peter算法小课堂—简单建模(2)

2023-12-14 22:41:41

太戈编程736题

题目描述:

你是一只汪星人,地球毁灭后你回到了汪星,这里每天有n个小时,你需要为自己选择正好连续的m小时作为每天睡眠的时间。从凌晨开始,第i小时内的睡眠质量为xi,请问经过选择后,你的睡眠质量总和最大是多少?

法1 断环+拉直+克隆

图示:

首先,这道题不是一般的前缀和问题,因为尾指针可以指向首指针。这个方法是普通方法,先拉直,再把数组复制一遍(所以数组至少要开两倍),然后算前缀和,最后扫一遍m+1到2*n,算差分最大值。写代码八

cin>>n>>m;
for(int i=1;i<=n;i++) cin>>x[i];
for(int i=n+1;i<=n*2;i++) x[i]=x[i-n];
s[0]=0;
for(int i=1;i<=n*2;i++) s[i]=s[i-1]+x[i];
int ans=s[m];
for(int i=m+1;i<=n*2;i++)
	ans=max(ans,s[i]-s[i-m]);
cout<<ans<<endl;

法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);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>x[i];
		x[i+n]=x[i];
	}
	for(int i=1;i<=m;i++) cur+=x[i];
	ans=cur;
	for(int i=2;i<=n;i++){
		int cur=cur-x[i-1]+x[i+m-1];
		ans=max(cur,ans);
	}
	cout<<ans<<endl;
	return 0;
}

就是一个滑动窗口,看起来比法1简洁

法3 首位情况分类

图示:

?

那么,先正常前缀和,再m-1次特判。

cin>>n>>m;
for(int i=1;i<=n;i++) cin>>x[i];
for(int i=1;i<=n;i++) s[i]=s[i-1]+x[i];
int ans=s[m];
for(int i=m+1;i<=n;i++)
	ans=max(ans,s[i]-s[i-m]);
for(int i=1;i<=m-1;i++)
	ans=max(ans,s[i]+s[n]-s[n-m+i]);
cout<<ans<<endl;

法4 循环单链表(数据结构)

因为这一个数据结构我没讲过,所以……我来给大家梳理一遍代码。先来看普通单链表八

结构体指针-CSDN博客

节点函数

typedef struct _node
{
	int data;
	struct _node *next;
}node;

创造链表

struct node *create(int n)
{
	node *head;
	node *tail;
	node *h;
	head=tail=(node*)(malloc)(sizeof(node));
	h=head;
	node *p;
	int i=n;
	int d=0;
	cout<<"Please input the intergers."<<endl;
	for(i=n;i>0;i--){
		p=(node*)(malloc)(size(node));
		cin>>d;
		p->data=d;
		p->next=NULL;
		tail->next=p;
		tail=p;
	}
	tail->next=h;
	return h;
}

?链表查找函数

struct node *search(node *head,node *s,int x){
	int y;
	while(s!=head){
		y=s->data;
		if(x==y) return s;
		else s=s->next;
	}
}

常见使用

int main(){
	int n;
	cin>>n;
	node *prt;
	prt=create(n);
	node *first;
	first=prt->next;
	node *pr;
	pr=first;
	while(first!=prt)
	{
		cout<<first->data<<" ";
		first=first->next;
	}
	int number;
	node *num;
	cout<<endl;
	cin>>number;
	num=search(prt,pr,number);
	cout<<num->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,第r+1个减j,这时再把差分数组化成前缀和数组,即可得到目标数组,时间复杂度O(1)

所以……上代码八

cin>>n;
for(int i=1;i<=n;i++){
	cin>>a>>b>>x;
	d[a]+=x;
	d[b+5]-=x;
}
for(int i=1;i<R;i++) s[i]=s[i-1]+d[i];
cout<<*max_element(s+1,s+1+n);

拓展:太戈编程2667

数据分类

int main(){
	freopen("training.in","r",stdin);
	freopen("training.out","w",stdout);
	input();
	if(n<=1000&&m<=1000) solveBF();
	else solve();
	return 0;
}

?BF

void solveBF(){
	for(l i=1;i<=m;i++){
		ll l,r;
		cin>>l>>r;
		ll ans=0;
		for(ll j=l;j<=r;++j) ans+=h[j]*(j-l+1);
		cout<<ans<<" ";
	}
}

满分解法

?

数学不好的请退出……

void solve(){
	for(ll i=1;i<=n;i++){
		s[i]=s[i-1]+h[i];
		g[i]=g[i-1]+h[i]*i;
	}
	for(ll i=1;i<=m;++i){
		ll l,r;
		cin>>l>>r;
		ll ans=g[r]-g[l-1]-(s[r]-s[l-1])*(l-1);
		cout<<ans<<" ";
	}
}

?希望这些对大家有用,三连必回。

文章来源:https://blog.csdn.net/zhang040818/article/details/135003907
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。