自动搬运

查看原文

来自洛谷，原作者为

	南城忆潇湘 今天又是摸鱼的一天

搬运于2025-08-24 22:06:23，当前版本为作者最后更新于2018-11-14 07:59:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解法1：
我有信仰，我是MC玩家，输出-1。预计得分：15.

解法2：
我会特判，处理ai=1,n=1的情况，预计得分：15.

解法3：
我会暴力，直接模拟。时间复杂度 $O(n^2)$ 。预计得分：30.

解法4：
我们发现，每次只要合并最小的两本书，然后合并。再往上找。找最小的两本书可以类似于合并果子，用优先队列做就好啦。预计得分：40-95(数据居然没有卡掉，还是那个-1的点卡常卡掉的23333).

解法5：
我们继续寻找规律，或者由合并果子的思路得来。这些附魔书合并前和合并后均有单调性，我们开两个队列就可以$O(n)$做。预计得分100.

解法6： 由于是两本合成一本附魔书，所以最坏情况下，附魔书的最大等级为$a[i]+log_2N$，我们就可以用递归来求解。开始只要桶排求出每种附魔书有多少本就可以了。递归有点小小的难打。预计得分100.

在这里附上50分代码和100分代码：

50pts:

#include<bits/stdc++.h>
using namespace std;
struct Node{
	int cost,lev,lei;
	friend bool operator < (Node x,Node y){
		if(x.lev==y.lev){
			if(x.cost==y.cost)	return x.lei>y.lei;
			return x.cost>y.cost;
		}
		return x.lev>y.lev;
	}
}x;
priority_queue <Node> q; 
int ans=0,cnt=214748347;
int ex_gcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int e=ex_gcd(b,a%b,y,x);
    y-=x*(a/b);
    return e;
}
int main(){
	int n,qwq,orz;
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%d",&x.lev),x.lei=1,x.cost=0,q.push(x);
	Node fir;
	while(q.size()>1){
		if(q.top().lev>ans)  ans=q.top().lev,cnt=q.top().cost;
		else if(q.top().lev==ans)	cnt=min(cnt,q.top().cost);
		fir=q.top();	q.pop();
		while(q.top().lev!=fir.lev)	fir=q.top(),q.pop();
		Node nxt,sec=q.top();
		nxt.cost=fir.cost+sec.cost+fir.lei+sec.lei;
		nxt.lei=max(fir.lei,sec.lei)*2+1;
		nxt.lev=fir.lev+1;
		q.pop(); q.push(nxt); 
	}
	if(q.top().lev>ans)  ans=q.top().lev,cnt=q.top().cost;
	if(ex_gcd(ans,cnt,qwq,orz)!=1)	cout<<-1<<endl;
	else{
		qwq=(qwq%cnt+cnt)%cnt;
		cout<<qwq<<endl;
	}
	return 0;
}

100pts:

#include<queue>
#include<cstdio>
#include<iostream>
#define int long long
#define MAXN 10000200
using namespace std;
int c[MAXN+50],d[MAXN+50],cnt,ans;
int ex_gcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int e=ex_gcd(b,a%b,y,x);
    y-=x*(a/b);
    return e;
}
int dg(int x){//获得一本等级为x的书的花费 
    if(d[x]){
        d[x]--;
        return 1;
    }	
    int p=dg(x-1),q=dg(x-1);
    ans+=p+q;
    return (max(p,q)*2+1) ;
}
inline void read(int &x){
    char ch;x=0;
    while(!isdigit(x))	ch=getchar();
    while(isdigit(x))	x=x*10+ch-'0',ch=getchar();
}
signed main(){
//	freopen("exp.in","r",stdin);
//	freopen("exp.out","w",stdout);
    int n,x,y;
    cin>>n;//cout<<"qwq"<<endl;
    for(int i=1;i<=n;i++){
        scanf("%lld",&x);
        d[x]++;c[x]++;
    }//cout<<"qwq"<<endl;
    for(int i=1;i<=MAXN;i++){
        c[i+1]+=c[i]/2;      c[i]%=2;
        if(c[i+1])	cnt=max(cnt,i+1);
    } //cout<<"qwq"<<endl;
    dg(cnt);
 	if(ex_gcd(cnt,ans,x,y)!=1)	cout<<-1<<endl;
    else{
        x=(x%ans+ans)%ans;
  		printf("%lld\n",x);
    }  
 //   cout<<ans<<" "<<cnt<<endl;
    return 0;
}