Codeforces Round #702 (Div. 3)

A：

题意：可以插入任意一个数使得序列a中所有相邻的两个数中较大的除以较小的要小于等于2，问最少要插入几个

思路：每次两个相邻的较大值除以较小值比值大于2，我们就让最小值扩大两倍，统计要扩大几次。

代码：

while(t--)
	{
		int n; cin >> n;
		for(int i=1;i<=n;i++)
		{
			cin >> a[i];
		}
		int sum=0;int cnt=0;
		for(int i=2;i<=n;i++)
		{
			int minn=min(a[i-1],a[i]);
			int maxn=max(a[i-1],a[i]);
			int tmp=ceil(1.0*maxn/minn);
			if((tmp)<=2) continue;
			else 
			{
				cnt=0;
				while(1)
				{
					minn*=2; cnt++;
					int tmp=ceil(1.0*maxn/minn);
					if(tmp<=2)
					{
						break;
					}
				}
			}
			sum+=cnt;
		}
		cout << sum << endl;
	}

B：

题意：每次操作你可以选择一个元素并将其加 1，问最少需要多少次操作，可以使得序列中对 3 取模分别等于 0、1、2 的元素个数相等。

思路：先统计下取模后为0 1 2个数各为多少，然后循环判断直到三者个数均为n/3。

代码：

while(t--)
	{
		int n; cin >> n;
		memset(b,0,sizeof(b));
		for(int i=1;i<=n;i++)
		{
			cin >> a[i];
			b[a[i]%3]++;
		}
		int tmp=n/3;
		int ans=0;
		while(b[0]!=tmp||b[1]!=tmp||b[2]!=tmp)
		{
			for(int i=0;i<3;i++)
			{
				if((b[i]>tmp))
				{
					b[(i+1)%3]++;
					b[i]--;
					ans++;
				}
			}
		}
		cout << ans << endl;
	}

C：

题意：给您一个正整数 x ，问这个正整数能否拆分成两个立方数之和。

思路：因为x最大1e12，用map标记1~10000的立方和，然后循环找x-i*i*i是否被标记过。

代码：

int t; cin >> t;
	map<ll,ll>mp;
	for(ll i=1;i<=10000;i++)
	{
		mp[i*i*i]=1;
	}
	while(t--)
	{
		ll x; cin >> x;
		int flag=0;
		for(ll i=1;i*i*i<x;i++)
		{
			if(mp[x-i*i*i]) 
			{
				flag=1;
				cout << "YES" << endl;
				break;
			}
		}
		if(!flag) cout << "NO" << endl;
	}

D：

题意：序列a里的最大值为树的根，该值左边的数为左子树，右边的数为右子树，如果该值左边没数则无左子树，右边同理。问以此方法构建树后各点的深度。根节点深度为0。

思路：dfs，找到最大值后依次搜该点的左边与右边，不断更新深度。l>r返回即可。

代码：

void dfs(int l,int r,int depth)
{
	int maxn=l;
	if(l>r) return ;
	for(int i=l;i<=r;i++)
	{
		if(a[i]>a[maxn]) maxn=i;//找到最大值的下标
	}
	ans[maxn]=depth;//标记该点的深度
	dfs(l,maxn-1,depth+1);
	dfs(maxn+1,r,depth+1);
}
int main()
{
    ios::sync_with_stdio;
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while(t--)
	{
		int n; cin >> n;
		for(int i=1;i<=n;i++)
		{
			cin >> a[i];
		}
		dfs(1,n,0);
		for(int i=1;i<=n;i++) cout << ans[i] << " ";
		cout << endl;
	}
    return 0;
}

E：

题意：有 n 支队伍参加比赛，每个队伍初始时有一些代币。比赛每一轮随机挑两个代币数不为0的队伍，然后代币多的队伍获胜，代币少的队伍把代币全部给代币多的（代币数量相同则随机），直到最后只有一个队伍有代币，这个队伍获胜。

思路：排序求前缀和。如果当前该点i的代币数大于前面i-1的前缀和，说明第i个人能赢，不断更新满足此条件人所在的位置k，最后根据式子n-k+1求出一共有多少人赢，然后处理下能赢的这些人的位置按照升序输出。

代码：

struct node{
	int v,p;//代币数，位置
};
bool cmp(node x,node y)
{
	return x.v<y.v;//按照代币数升序排列
}
int main()
{
    ios::sync_with_stdio;
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while(t--)
	{
		int n; cin >> n;
		node t[n+5];
		for(int i=1;i<=n;i++) 
		{
			cin >> t[i].v;
			t[i].p=i; //标记位置
		}
		sort(t+1,t+1+n,cmp);
		int k=-1;
		for(int i=1;i<=n;i++) sum[i]=sum[i-1]+t[i].v;
		for(int i=1;i<=n;i++) {
			if(t[i].v>sum[i-1]) k=i;
		}
		cout << n-k+1 << endl;
		ll cnt=0;
		for(int i=k;i<=n;i++) 
		{
			ans[++cnt]=t[i].p;
		}
		sort(ans+1,ans+1+cnt);
		for(int i=1;i<=cnt;i++) cout << ans[i] << " ";
		cout << endl;
	}
	return 0;
}

F：

题意：问原序列a中要删除多少个数字才能使得新序列中不相同的数字个数相等。

思路：开个桶，存一下有多少种不同的数字且各数字都有几个，然后排序求前缀和，枚举每个数，每个数前面的都都删了，因为个数小于当前数字i的各数，即每次删除sum[i-1]，再把大于数字i的数的个数减成跟数字i一样即可。式子为：sum[i-1]+sum[n]-sum[n-1]+(n-i)*b[i]，n为一共有n种不同的数组，数组b为该数有b[i]个，每次取最小值。

代码：

while(t--)
	{
		int n; cin >> n;
		map<int,int>mp;//用map标记一共有多少种数组
		for(int i=1;i<=n;i++)
		{
			int x; cin >> x;
			mp[x]++;
		}
		int S=mp.size();//一共有S种数字 
                int cnt=0;
		for(auto i : mp)
		{
			b[++cnt]=i.second;
		}
		sort(b+1,b+1+S);
		sum[0]=0;
		for(int i=1;i<=S;i++)
		{
			sum[i]=sum[i-1]+b[i];
		}
		sum[S+1]=0;
		ll ans=INF;
		for(int i=1;i<=S;i++)
		{
			ans=min(ans,sum[i-1]+sum[S]-sum[i]-(S-i)*b[i]);
		}
		cout << ans << endl;
	}

G：