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\)，则应增加一些项目，有以下两种可能：
- 新加一个 \(a_i\)
- 新加一个 \(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;
}