一定要好好睡觉啊，不然打模拟赛的时候会困死的！！！
非常非常困的7:50时就开始打模拟赛，还是打了四个小时。打了T1、T2的正解，T3的5分特殊样例、T3的10分特殊样例，预计总215分。
然后经过漫长的三个小时的等待，出现了 T1 100分，T2 65分，T3 60分，T4 10分、总分235分 的神奇成绩。虽然结果比预估的高，但我的T2挂了整整35分！这让我非常的不爽。当我发现是因为没开long long时，不开心的心情到达了顶峰————
不然我就可以排名第二了！！
T1【恋曲】
题目大意：
给出n,t,x，与长度为n(1<=n<=1e6)的两个序列a,b。每次操作可以使ci=min(ci+bi,ai)，最多操作t(1<=t<=1e9)次，问是否可以使∑ci>=x(ci初始化为0)
解题思路：
感觉可以贪心。每次操作花费代价一定，所以能取大的bi就取。于是乎，想到用大根堆维护最大值，类型为pair<int,int>，第一个为bi，第二个为可使用的次数。我们注意到，对于每个bi可以分为两个部分，一部分是每次取bi，一共可取ai/bi(下取整)次；另一部分是取ai%bi，只可以取一次(总和ai可以分成大小为bi的若干整份，但总会剩下分不成bi的一份)，在输入时预处理为两部分、插入大根堆即可。
完了后每次取堆顶，然后操作，判断操作次数与总和的边界输出即可。
可爱的小代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,t,x;
int a[N],b[N];
long long sum;
long long tol;
priority_queue < pair<int,int> > q;
void read()
{
scanf("%d%d%d",&n,&t,&x);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
for (int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
if (b[i]>a[i]) b[i]=a[i];//防止溢出
q.push(make_pair(b[i],a[i]/b[i]));
if (a[i]%b[i]) q.push(make_pair(a[i]%b[i],1));
}
}
int main()
{
read();
if (sum<x)//就算全部取到也不够
{
printf("No");
return 0;
}
while (!q.empty())
{
int bb=q.top().first,dd=q.top().second;
q.pop();
tol+=min(dd,t)*bb;
t-=min(t,dd);
if (t==0)//边界
{
if (tol>=x) printf("Yes");
else printf("No");
break;
}
if (tol>=x)//边界
{
printf("Yes");
break;
}
}
return 0;
}
T2【留校丕】
题目大意：
给出一个长度为n(2<=n<=1e6)的序列p(保证p是排列)，每次操作可以交换p中相邻的两个数，求使p变成单峰的最小操作次数
解题思路：
本来想的p中最大值一定是会是那个“峰”，但显然看最大值很不好操作。通过群中fjj思路的启示，我们想到p中的最小值一定需要在序列两边；又因为每次操作只能交换相邻的两个数，所以移动最小值后序列中的其他数不变（比如序列3 1 2 4 5，不论是将1移到序列左边或是右边，3 2 4 5的序列位置都没有改变）。
于是乎，可以把移动mn看作删除mn(显而易见，mn是指当前序列中的最小值)，那么每次移动一定要往移动次数少的一边移动，这样的贪心才可使ans最小。但是因为“删除mn”的操作，序列中数的个数会发生改变，也就是说我们要对这个序列进行单点修改与区间查询，一下子就想到了树状数组。但是，作为一个大蒟蒻，我只能写一个线段树来(还好没被卡)。
但!是!不!要!忘!记!ans!要!开!long!long!
不可爱的小代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int n;
int p[N],t[N];
int pos[N];
int sum[N*4];
long long ans;
void read()
{
scanf("%lld",&n);
for (int i=1;i<=n;i++)
{
scanf("%lld",&p[i]);
pos[p[i]]=i;//记录一下每个值的位置
}
}
void pushup(int id)
{
sum[id]=sum[id*2]+sum[id*2+1];
}
void build(int id,int l,int r)
{
if (l==r)
{
sum[id]=1;
return ;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
pushup(id);
}
int query2(int id,int l,int r,int i,int j)
{
if (j==0||i==n+1) return 0;//特判目前最小值已在序列边界 不然会死循环
if (l>=i&&r<=j) return sum[id];
int mid=(l+r)/2,sm=0;
if (i<=mid) sm+=query2(id*2,l,mid,i,j);
if (mid+1<=j) sm+=query2(id*2+1,mid+1,r,i,j);
return sm;
}
void del(int id,int l,int r,int x)
{
if (x==l&&x==r)
{
sum[id]-=1;
return ;
}
int mid=(l+r)/2;
if (x<=mid) del(id*2,l,mid,x);
if (mid+1<=x) del(id*2+1,mid+1,r,x);
pushup(id);
}
signed main()
{
read();
build(1,1,n);//建树
int mn=0;//序列当前最小值
for (int i=1;i<=n;i++)
{
mn++;
ans+=min(query2(1,1,n,1,pos[mn]-1),query2(1,1,n,pos[mn]+1,n));//取移到最左边、最右边的更小值
del(1,1,n,pos[mn]);
}
printf("%lld",ans);
return 0;
}
标签：2024.10,int,31,mn,T2,bi,long,序列,模拟 From： https://www.cnblogs.com/Myyy-L/p/18518620