Living-Dream 系列笔记 第22期

Problem

T1

/*
思路：
因为题目要求最大水量，所以K次操作需要都用上，
并且由于每次都是将x倒入x+1中,所以K次操作之后的最大水量应当是x~x+k+1之和；
于是问题就转变成了求一段长度为k+1的连续子段的和的最大值，因此维护一个前缀和即可。
*/
#include<bits/stdc++.h>
using namespace std; 
#define int long long

int n,k,ans=-1e9;
int a[1000031],sum[1000031];

signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++) 
		cin>>a[i],sum[i]=sum[i-1]+a[i];
	for(int i=1;i+k<=n;i++){
		int l=i,r=i+k;
		ans=max(ans,sum[r]-sum[l-1]);
		//cout<<sum[r]-sum[l-1]<<'\n';
	}
	cout<<ans;
	return 0;
}

T2

/*
思路：
很显然h指数具有单调性，因此我们考虑二分答案。
如何设计check函数？仅需根据h指数的定义，
扫描N篇论文，计算是否有h篇引用次数>=h即可。
但是还有K篇综述如何处理？根据贪心策略，
我们尽可能地将K篇综述都放在引用次数最大的K篇中，
这样需要补齐的引用次数越少，
能达到引用次数>=h的论文就越多，
答案就会更优，
因此我们必须先对c数组降序排序。
注意对于每一篇论文仍需判断若h-ci>k则h一定不合法，
因为一篇论文只有可能被K篇综述依次引用，
即最多额外增加K的引用次数，
既然K次都不够，那么因为c数组已经降序排序，所以后面的差会更大，
这样就说明此时的h一定不合法。
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long

int n,k,l;
int a[100031];

bool cmp(int x,int y){ return x>y; }
bool check(int x){
	int sum=0;
	for(int i=1;i<=n;i++){
		if(a[i]<x){
			sum+=x-a[i];
			if(x-a[i]>k) return 0;
		}
		if(sum>k*l) return 0;
		if(i==x) return 1;
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>k>>l;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1,cmp);
	//memcpy(tmp,a,sizeof(tmp));
	
	int lt=0,rt=n+1;
	while(lt+1<rt){
		int mid=(lt+rt)>>1;
		if(check(mid)) lt=mid;
		else rt=mid;
	}
	cout<<lt;
	return 0;
}

T3

/*
思路：
因为T过大，所以考虑O(n)做法。
我们想到只有di天是有变化的，其他天都是单调不变的。
而每次di天之后到d{i+1}天之前的那些天都是吃的di天送来的干草，
即那些天吃的干草总量为min(剩余干草总量,d{i+1}-di)。
因此我们拿一个sum记录剩余干草总量，now记录那些天吃的干草总量。
每次令now=min(sum,d{i+1}-di),sum=sum-now+bi，
并且令答案累加sum即可。
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long

int n,t,ans,sum;
int d[100031],b[100031];

signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>t;
	for(int i=1;i<=n;i++) cin>>d[i]>>b[i];
	for(int i=1;i<=n;i++){
		int now=min(sum,d[i]-d[i-1]);
		sum=sum-now+b[i];
		ans+=now;
	}
	cout<<ans+min(sum,t-d[n]+1);
	return 0;
}

T4

/*
思路：
考虑一种贪心策略：
对于每一头牛，若在其范围内没有可以吃的草，则在其范围的右边界处种草。
这样的贪心策略也很容易证明：
若存在一个位置p<右边界，且在p处种草比在右边界种草更优，
则设p能管辖它右边x头牛，而右边界能管辖y头，
根据常识，y一定不小于x，因此在p处种草一定不比在右边界种草更优。
于是我们分别处理G牛和H牛，根据以上述贪心策略种草即可。
但是有一个漏洞：
若为H牛种草时其中有一头牛的右边界到达了n，而n处恰好种了草。
首先这种情况只可能出现在n处，因为H牛和G牛不会重叠。
对于这种情况，仅需从n-1处开始倒序枚举草地，直到当前草地没有被种草，
此时在这个位置种下H牛的草即可。
但是，还有一个问题：
如果按照上述思路，
在循环内朴素枚举判断每一头牛的范围内是不是有可以吃的草，
这样会TLE。
于是我们想到使用一个变量来记录上次放置的草的位置，
因为我们是顺次遍历所有牛，所以草的顺序一定是单调递增的，
所以我们对于每一头牛，仅需判断上次放置草的位置是否在其范围内即可。
*/
#include<bits/stdc++.h>
using namespace std;

int T,n,k,cnt,lastg,lasth;
char s[100031],ans[100031];

int main(){
	cin>>T;
	while(T--){
		cin>>n>>k>>s;
		for(int i=0;i<n;i++) ans[i]='.';
		cnt=0; lastg=lasth=-1e9;
		
		for(int i=0;i<n;i++)
			if(s[i]=='G'&&(lastg<max(0,i-k)||lastg>min(n-1,i+k)))
				ans[min(n-1,i+k)]='G',cnt++,lastg=min(n-1,i+k);
			
		for(int i=0;i<n;i++){
			if(s[i]=='H'&&(lasth<max(0,i-k)||lasth>min(n-1,i+k))){
				if(min(n-1,i+k)==n-1&&ans[n-1]=='G'){
					int j=n-2;
					while(ans[j]=='G') j--;
					ans[j]='H',lasth=j,cnt++;
				}
				else 
					ans[min(n-1,i+k)]='H',lasth=min(n-1,i+k),cnt++;
			}
		}
		
		cout<<cnt<<'\n';
		for(int i=0;i<n;i++) cout<<ans[i];
		cout<<'\n';
	}
	return 0;
}