首页 > 其他分享 >20241031模拟赛题解

20241031模拟赛题解

时间:2024-10-31 17:19:36浏览次数:8  
标签:10 ch int 题解 namespace Alice Bob 20241031 模拟

T1

题目描述

给定一个圆形蛋糕,被 \(n\) 条切割线分成 \(n\) 个扇形蛋糕块,按照顺时针编号,第 \(i\) 块上有 \(a_i\) 个草莓,第 \(i\) 条切割线到第 \(i+1\) 条切割线之间的部分是第 \(i\) 块蛋糕。

Alice 和 Bob 流选择切割线,假设 Alice 选择了第 \(i\) 条切割线,Bob选择了第 \(j\) 条切割线,\(j\) 不能等于 \(i\)。则 Alice 获得从第 \(i\) 条切割线顺时针到第 \(j\) 条切割线之间的蛋糕,Bob获得剩余蛋糕。Alice 的平均草莓数若大于等于 Bob 的平均草莓数,则 Alice 获胜,否则 Bob 获胜。求使 Alice 必胜的最小切割线编号,不存在则输出 \(-1\)。

输入格式

第一行一个正整数 \(n\)

第二行 \(n\) 个正整数 \(a_i\) 表示第 \(i\) 块内的草莓数量。

输出格式

一个整数,即为答案。

样例

样例输入1

3
3 8 5

样例输出1

2

Alice 在 \(3\) 和 \(8\) 之间切一刀,Alice要么会拿到 \(8\) 要么会拿到 \(8\) 和 \(5\),都可以获胜。

数据范围

对于所有数据 \(1<n≤500000,1≤ai≤500000\)。

对于 \(50 \%\) 的数据 \(n≤1000\)。

对于 \(100 \%\) 的数据无特殊限制。

解法说明

可将每个 \(a_i\) 转化为其与所有数字的平均值之间的差,对新的 \(a_i\) 做前缀和,则当 Alice 选 \(i\),Bob 选 \(j\) 时,如 \(sum_{j-1} - sum_{i-1} ≥ 0\),则 Alice 胜。故 Alice 应选 \(sum_{i-1}\) 最小的点后面的切割线,此时无论 Bob 如何选择都必败。

通过代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=5e5+10;

namespace IO{
	inline int read(){
		int x=0,f=1;char ch=getchar();
		while(ch<'0'||ch>'9') f=(ch=='-'?-1:f),ch=getchar();
		while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
		return x*f;
	}

	inline void write(int x){
		if(x<0) putchar('-'),x=-x;
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
}using namespace IO;

namespace code{
	int n,a[N],sum[N],ans;

	void solve(){
		n=read();
		for(int i=1;i<=n;i++) a[i]=read(),sum[i]=sum[i-1]+a[i];
		for(int i=1;i<=n;i++) a[i]=a[i]*n-sum[n];
		for(int i=1;i<n;i++) sum[i]=sum[i-1]+a[i],ans=(sum[i]<sum[ans]?i:ans);
		write(ans+1);
	}
}

signed main(){
	code::solve();
	return 0;
}

T2

题目描述

游乐园有 \(n\) 个项目,第 \(i\) 个项目直接排队要 \(a_i\) 分钟,使用优速通需要排队 \(b_i\) 分钟。你有 \(k\) 张优速通票,也就是意味着你可以选不超过 \(k\) 个项目使用优速通。你一共有 \(t\) 分钟,这里忽略除了排队以外的其他时间。你想知道你最多可以玩多少个不同的项目。

输入格式

第一行三个正整数 \(n\),\(k\),\(t\)。

接下来 \(n\) 行,每行两个正整数 \(a_i\),\(b_i\)。

输出格式

一个整数,即最多能玩的项目数量。

样例

样例输入1

5 2 20
7 4
10 8
3 3
8 7
9 5

样例输出1

4

数据范围

对于所有数据 \(1≤k≤n≤2×10^5,1≤T≤10^{18}, 1≤b_i≤a_i≤10^{12}\)

对于 \(20\%\) 的数据:\(n≤10\)。

对于 \(50\%\) 的数据:\(n≤1000\)。

对于 \(100\%\) 的数据:无特殊限制。

解法说明

反悔贪心。

显然,前 \(k\) 个肯定是 \(b_i\) 能选几个是几个。如果选完后 \(t>0\),则应增加一些项目,有以下两种可能:

  1. 新加一个 \(a_i\)
  2. 新加一个 \(b_i\),并将一个选过的 \(b_j\) 换成 \(a_j\)。

此时我们可以开三个堆,一个存储未选过的 \(a_i\),另一个存储未选过的 \(b_i\),最后一个存储选过的 \(a_j - b_j\)。记三个堆堆顶分别为 \(u\)、\(v\)、\(w\),则如果 \(u<v+w\) 选择第一种,否则选择第二种,不停循环直到 \(t<0\) 为止。

通过代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define PII pair<int,int>
#define mp make_pair
const int N=2e5+10;

namespace IO{
	inline int read(){
		int x=0,f=1;char ch=getchar();
		while(ch<'0'||ch>'9') f=(ch=='-'?-1:f),ch=getchar();
		while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
		return x*f;
	}

	inline void write(int x){
		if(x<0) putchar('-'),x=-x;
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
}using namespace IO;

namespace code{
	int n,k,t,ans;
	bool vis[N];
	
	struct node{
		int a,b;
	}a[N];
	
	priority_queue<PII,vector<PII>,greater<PII> > q1,q2,q3;
	
	bool cmp(node x,node y){
		return x.b<y.b;
	}

	void solve(){
		n=read(),k=read(),t=read();
		for(int i=1;i<=n;i++) a[i].a=read(),a[i].b=read();
		sort(a+1,a+n+1,cmp);
		for(int i=1;i<=k&&t>=0;i++,ans++) t-=a[i].b,vis[i]=1;
		if(t<0) return write(ans-1),void();
		for(int i=1;i<=n;i++){
			if(!vis[i]) q1.push(mp(a[i].a,i)),q2.push(mp(a[i].b,i));
			else q3.push(mp(a[i].a-a[i].b,i));
		}
		while(t>0){
			int x=q1.top().second,y=q2.top().second,u,v,w;
			while(vis[x]) q1.pop(),x=q1.top().second;
			while(vis[y]) q2.pop(),y=q2.top().second;
			ans++,u=q1.top().first,v=q2.top().first,w=q3.top().first;
			if(u<v+w) q1.pop(),vis[x]=1,t-=u;
			else q2.pop(),q3.pop(),vis[y]=1,t-=v+w,q3.push(mp(a[y].a-a[y].b,y));
		}
		write(t<0?--ans:ans);
	}
}

signed main(){
	code::solve();
	return 0;
}

标签:10,ch,int,题解,namespace,Alice,Bob,20241031,模拟
From: https://www.cnblogs.com/Alexxtl/p/18518466

相关文章

  • 模拟用户登录网站
    模拟用户登录网站requests模块Requests继承了urllib2的所有特性。Requests支持HTTP连接保持和连接池,支持使用cookie保持会话,支持文件上传,支持自动确定响应内容的编码,支持国际化的URL和POST数据自动编码。requests的底层实现其实就是urllib3Requests的文档非常完备,中文......
  • NOIP 模拟赛:2024-10-28
    T1:给定两个数组\(a,b\),要求将\(b\)重排,使得\(b>a\)的位置个数最多,在此基础上最大化\(b\)的字典序。\(n\le5000\)。最多的位置个数是容易求的,排个序即可。如何最大化字典序?依次枚举\(i=1\simn\),然后从大到小枚举\(j\)看看\(b_i=j\)是否可以让后面依然保持大于位......
  • 【10-31模拟赛T1】四舍五入
    给出\(n\),对于任意正整数\(i\)满足\(1\leqi\leqn\),求有多少个正整数\(j\)满足\(1\leqj\leqn\)且\(i\bmodj\leq\frac{j}{2}\)。枚举\(i\)不好处理,可以反过来,外层枚举\(j\),内层枚举左右端点\(l=kj,r=kj+\lfloor\frac{j}{2}\rfloor\)(\(k\)为自然......
  • 模拟信号和数字信号之间的区别
    ​​模拟信号和数字信号之间的区别:1.信号的表示方式;2.信号的处理和传输;3.抗干扰能力;4.存储和复制;5.应用场景。模拟信号和数字信号作为信息载体,在通信领域内扮演着核心角色。模拟信号以连续变化的方式表征信息,而数字信号则以离散数值形式存在。1.信号的表示方式模拟信号的连续......
  • 基于SSM学生竞赛模拟系统的设计
    管理员账户功能包括:系统首页,个人中心,用户管理,公告信息管理,试题管理,论坛交流,试卷管理,系统管理前台账号功能包括:系统首页,个人中心,公告信息,论坛交流,试卷,校园资讯开发系统:Windows架构模式:SSMJDK版本:JavaJDK1.8开发工具:IDEA(推荐)数据库版本:mysql5.7数据库可视化工具:navic......
  • Codeforces Global Round 27,D. Yet Another Real Number Problem 题解
    单调栈+贪心题意:给定一个序列从左往右对于每个索引iii,求出其前缀的数组可以进行任意次以下操作的条件下:选择......
  • 2024CCPC哈尔滨部分题解
    赛时被评测机卡死了M.奇怪的上取整求\(\sum_{i=1}^{n}f(n,i)\)\(Input\)第一行一个整数\(T(1<=T<=10^3)\),表示数据组数对于每组数据,一行一个整数\(n(1<=n<=10^9)\)\(Output\)对于每组数据,输出一行一个整数,表示答案。\(Sample\)35451114514————————21T10......
  • 【Unity】UGUI模拟NGUI的UISprite-->LImage
    UGUI本没有像NGUI方便使用图集的组件,之前也写过继承Image,加入SpriteAtlas作图集,切换图片显示的组件,现在弄一个3.0版本的这个组件的诞生源于上一篇:【Unity】Addressables下的图集(SpriteAtlas)内存优化==========================================================================......
  • Apache Commons Net 共享SSLSession问题解决
        某些服务器会默认开启TLS会话恢复,如FileZillaServer1.0及以后的版本(相对于1.0以前版本就是先当与勾选了RequireTLSsessionresumptionondataconnectwhenusingPORTP)。ApacheCommonsNet目前是不支持TLS会话恢复的,所以我们只能通过重写FTPSClient来实现。不然你......
  • ZZJC新生训练赛第十二场题解
    难度分类(同一难度下按字典序上升)入门:G简单:C,E,A中等:F,D,B困难:HG-解题思路按照题意模拟即可G-代码实现#include<bits/stdc++.h>intmain(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::strings;......