牛客 CSP-J入门组 简单排序

我以为的排序->sort自定义
实际的排序->与大量算法综合考察，甚至还考推导公式

问题一:
求和
走这

问题分析：

1. 一开始是用间距写的，思路是间距最多到n/3,但实际是错误的，当1~9的时候间距能取到4，1到13同理(但我现在还是不知最大能到几)(我可真是菜…)
2. 修正了后只能在洛谷拿到40分，其他全部TLE,看了下数据范围，如果O（n^2）到了10000000000
3. 看了题解才发现有公式可推…

以下结合AC代码说明

#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct lat{
	int color;
	int nums;
	bool ji;//1表奇 2表偶
	int id;	
};
struct cp{
	bool operator()(lat t1,lat t2)
	{
		if(t1.color==t2.color)
		{
			if(t1.ji==t2.ji)
			{
				return t1.id<t2.id;
			}
			else{
				return t1.ji<t2.ji;
			}
		}else{
			return t1.color<t2.color;
		} 
	}
};
lat lats[100010];
ll sum; 
ll cnt[100010][3]; 
ll cnts[100010][2]; 
int main()
{
	/*
	题目要求：y-x=z-y,而x与z的color必须相同,题目除了第一个条件与y毫无关系
	x+z=2*y(说明x与z同奇偶) ,不同颜色、奇偶的x、z不会产生分数 
	根据奇偶颜色相同将格子 分为1组 
	*/ 
	int n,m;
	cin>>n>>m; 
	ll sum = 0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&lats[i].nums);
		//sum+=(lats[i].nums);公式的sum是奇偶相同颜色相同的sum 
		lats[i].id = i;
		if(i%2==0)
		{
			lats[i].ji = 0;
		}else{
			lats[i].ji = 1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&lats[i].color);
		if(lats[i].ji==1)
		{
			cnt[lats[i].color][1]++;//计数 
			cnts[lats[i].color][1]+=lats[i].nums;
		}else{
			cnt[lats[i].color][0]++;
			cnts[lats[i].color][0]+=lats[i].nums; 
		}
	}
	sort(lats+1,lats+n+1,cp());
	/*先计数有多少个颜色奇偶相同在一组*/
	ll sumqi = 0;
	ll sumou = 0;
	ll res = 0;
	for(int i=1;i<=n;i++)
	{
		if(lats[i].ji&&cnt[lats[i].color][1]>=2)//如果为奇数 
		{
			sumqi = ((cnt[lats[i].color][1]-2)*lats[i].nums*lats[i].id+lats[i].id*cnts[lats[i].color][1])%10007;
			res+=sumqi;
			res%=10007;
		}
		if(!lats[i].ji&&cnt[lats[i].color][0]>=2)
		{
			sumou = ((cnt[lats[i].color][0]-2)*lats[i].nums*lats[i].id+lats[i].id*cnts[lats[i].color][0])%10007;
			res+=sumou;
			res%=10007;
		}
	}
	printf("%lld\n",res);
}   

1. 假设存在这样一组，那么就可以推导公式了，将(1,2)(1,3)…(1,n)的分数求和，用分配律即可发现公式即
   (cnt-2)×id×nums[id]+id×(同奇偶同颜色的格子和)
2. 根据分别统计即可

问题二：
不简单的排序
走这

问题分析：

1. 虽然提示了可能已经排好序了但我还是用了快排+直接插入排序，结果显示TLE，最后看了答案才发现用优化的冒泡排序即可…
2. 如果已经排好序了，那么，冒泡排序的时间复杂度就是O(n),比快速排序快

AC代码：

#include <bits/stdc++.h>
using namespace std;
int nums[1500010];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&nums[i]);
	}
	for(int i=0;i<n-1;i++)
	{
		bool flag = false;
		for(int j=0;j<n-i-1;j++)
		{
			if(nums[j]>nums[j+1])
			{
				swap(nums[j],nums[j+1]);
				flag = true;
			}
		}
		if(!flag)
		{
			break;
		}
	}
	for(int j=0;j<n;j++)
       printf("%d ",nums[j]);
    return 0;
}

问题三：
国王的游戏

走这

问题分析：

1. 完全莫得思路，体感就是最后一位大臣获得最多的钱(实际不是)，结果看了题解发现又双有规律可循
2. 由公式推导可得，当按照左右手积排序时，后面的大臣就可以获得最优解，（但也不一定，测试点有所有大臣的左手积小于右手数字的情况）
3. 因此要在每次除以大臣的右手时对大臣判断是否为最大值
4. 最重要的是：这里要用到高精除和高精乘，因为每次都要累乘所以乘积是不能被除法改变的！！！，而商每次都要清零

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct people{
	ll left;
	ll right;
	ll mul;
};
people p[1010];
ll nums[30000] ={0,1};//1位初始化为1 ,nums[0]取位数 
ll res[30000];
ll ans[30000];
int r = 1;
int k = 1;//存储位数 
int m;//真答案的位数 
struct cp{
	bool operator()(people p1,people p2)
	{
		return p1.mul<p2.mul;
	}
};
void multiple(ll x)
{
	//进位 
	for(int i=1;i<=k;i++)
	{
		nums[i]*=x;
	}
	for(int i=1;i<=k;i++)
	{
		nums[i+1]+=nums[i]/10;
		nums[i]%=10;
	}
	while(nums[k+1]!=0)
	{
		k++;
		nums[k+1] = nums[k]/10;
		nums[k]%=10;
	}
}
void divide(ll x)//高精除
{
	memset(res,0,sizeof(res));//每次都要获得新的商 
	ll tmp = 0;
	r = k;//如果不用r存位数，那么积的位数就会改变，乘积就会错误 
	for(int i=r;i>0;i--)
	{
//		res[i] = nums[i]/x;//每次除把之前的nums改变了 
//		
//		nums[i-1] += ((nums[i]-res[i]*x)*10);//0位存余数
         tmp*=10;
         tmp+=nums[i];//用变量就不会改变nums的值 
         res[i] = tmp/x;
         tmp%=x;//不是取余10,如果x>10,那么商就是错误的 
	}
	while(res[r]==0&&r>1)
	{
		r--;
	}
} 
bool compares()
{
	if(m<r) return 1;
	if(m>r) return 0;
	if(m==r)
	{
		for(int i=m;i>0;i--)
		{
			if(res[i]>ans[i])
			{
				return 1;
			}
			else if(res[i]<ans[i])
			{
				return 0;
			}
			else {
				continue;
			}
		}
	}
}
void maxs()
{
	memset(ans,0,sizeof(ans)) ;
	for(int i=1;i<=r;i++)
	{
		ans[i] = res[i];
	}
	m = r;
}
int main()
{
	int n;
	cin>>n;
	cin>>p[0].left>>p[0].right;
	for(int i=1;i<=n;i++)
	{
		cin>>p[i].left>>p[i].right;
		p[i].mul = p[i].left*p[i].right;
	}
	/*根据规律，要最后一位大臣获取金币最少，那么left*right大的排在后面
	更能获得最优解 ，但要注意，不一定是最后一位就能获得最大值 
	*/
	sort(p+1,p+n+1,cp());
	/*n<=1000,且a、b<10000,10000的1000次方必然用高精*/
	for(int i=0;i<n;i++)//每获得一次结果就要与上一次比较 
	{
		multiple(p[i].left);
		divide(p[i+1].right);
		if(compares())//每除法会改变k的值，因此需要保护k，以便
		//乘积正常 
		{
			maxs();
		}
	}
	bool flag = true;
	
	for(int i=m;i>0;i--)//这个如果是0就输出不了 
	{
		if(ans[i]!=0)
		{
			flag = false;
		}
		if(!flag)
		{
			cout<<ans[i];
		}
	}
	cout<<endl;
} 

找bug找了几个小时…

问题四：
瑞士轮
走这

问题分析：

1. 绝了，自己写的代码只能在牛客过，而洛谷四个TLE，看来排序还要优化
2. 要注意通过函数修改结构体变量的值时，要加上引用符号否则不会改变
3. 快排比归并排序更适合数据量大的情况，而每次比较相邻区间用归并排序更好，但他们都比sort快

牛客的AC代码：

#include <bits/stdc++.h>
using namespace std;
struct player{
	int id;
	int power;
	int score;
};
player p[200010];
struct cp{
	bool operator()(player p1,player p2)
	{
		if(p1.score==p2.score)
		{
			return p1.id<p2.id;
		}
		else{
			return p1.score>p2.score;
		}
	}
};
void play(player& p1,player& p2)
{
	if(p1.power>p2.power)
	{
		p1.score++;
		//p2.score--;
	}else{
		//p1.score--;
		p2.score++;
	}
}
int main()
{
	int n,r,q;
	cin>>n>>r>>q;
	for(int i=1;i<=2*n;i++)
	{
		cin>>p[i].score;
		p[i].id = i;
	}
	for(int i=1;i<=2*n;i++)
	{
		cin>>p[i].power;
	}
	sort(p+1,p+2*n+1,cp());
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=2*n;j+=2)
		{
			play(p[j],p[j+1]);
		}
		sort(p+1,p+n*2+1,cp());
	}
	cout<<p[q].id<<endl;
} 

再分析：

1. 每次比赛结束后，胜者和负者的顺序已经确定了，而sort更适合无序序列，并且每次排序都是打乱重来，而归并排序只要将胜者和负者这些有序序列归并即可（即归并更适合有序序列）

洛谷AC代码：

#include <bits/stdc++.h>
using namespace std;
struct player{
	int id;
	int power;
	int score;
};
player p[200010];
player wins[100010];
player loser[100010];
struct cp{
	bool operator()(player p1,player p2)
	{
		if(p1.score==p2.score)
		{
			return p1.id<p2.id;
		}
		else{
			return p1.score>p2.score;//错误3：score写成了power 
		}
	}
};
int main()
{
	ios::sync_with_stdio(0);
	int n,r,q;
	cin>>n>>r>>q;
	for(int i=1;i<=2*n;i++)
	{
		cin>>p[i].score;
		p[i].id = i;
	}
	for(int i=1;i<=2*n;i++)//错误1：没有*2 
	{
		cin>>p[i].power;
	}
	sort(p+1,p+2*n+1,cp());
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=2*n;j+=2)
		{
			if(p[j].power>p[j+1].power)
	      {
		     p[j].score++;
	      }else{
		     p[j+1].score++;
	      }
		}
		stable_sort(p+1,p+n*2+1,cp());//基于归并排序实现 
	}
	cout<<p[q].id<<endl;
}

问题五
P1158 导弹拦截
走这

问题分析：

1. 说实话，完全没有思路，但后来想到对所有导弹距离系统的距离进行排序，从最小的距离开始dfs，到最大的距离为止，但是我写的代码显示不出结果(菜是原罪)
2. 看了题解发现是先对系统1的距离进行排序，然后再一个个枚举到系统二中，选出最小的平方和即可(我真的好菜555)
3. 要注意的点是，既然求得是平方和，那么我们算距离的时候不用开方，这样还能省去精度问题
4. 可能会用到非常规下标的情况，因为不能漏掉全交给1和全交给2的情况

AC代码：

#include <bits/stdc++.h>
using namespace std;
struct bomb{
	int x;
	int y;
	int dest1;
	int dest2;
};
struct cp1{
	bool operator()(bomb b1,bomb b2)
	{
		return b1.dest1<b2.dest1;
	}
};
bomb b[100010];
int n; 
int main()
{
	/*先将所有导弹到1号系统的距离进行排序，从最远方开始依次裁掉导弹 
	*/
	ios::sync_with_stdio(0);
	int x1,y1,x2,y2;
	cin>>x1>>y1>>x2>>y2;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>b[i].x>>b[i].y;
		b[i].dest1 = (pow(abs(b[i].x-x1),2)+pow(abs(b[i].y-y1),2));
		b[i].dest2 = (pow(abs(b[i].x-x2),2)+pow(abs(b[i].y-y2),2));
	}
	sort(b+1,b+1+n,cp1());
	int r2 = 0;
	int mins = 0xfffffff;//此时的平方和最小值 
	b[0].dest1 = 0;//避免漏掉全交给第二个系统的情况 
	b[n+1].dest2 = 0; //不从n+1开始会漏掉全交给第一个系统的情况 
	for(int i=n+1;i>0;i--)//将第一个系统能拦截的导弹线性排列 
	{
	     r2 = max(r2,b[i].dest2);//b[i].dest2定义为
		//拦截i~n颗导弹的最远距离
		mins = min(r2+b[i-1].dest1,mins); 
	}
	
	cout<<mins;
}

本文地址：https://blog.csdn.net/sky666tzz/article/details/109982634