NOIP2016模拟赛-大水题引发的惊天血案

发布于 2016-11-16  3110 次阅读


这是今天在洛谷上的一次模拟赛的第一题。

题意大概是这样的:

题目背景

kkk在赛车~

题目描述

现在有N辆赛车行驶在一条直线跑道(你可以认为跑道无限长)上。它们各自以某种速度匀速前进,如果有两辆车A车和B车,A车在B车的后面,且A车的速度大于B车的速度,那么经过一定的时间后,A车必定会超过B车,这称为一次超车。求超车总数。道路起点的位置为0,没有两辆车的初始位置相同。

这一看就是大水题嘛~~

于是代码一口气就出来了:

#include<iostream>
#include<iomanip>
#include<cstring>
using namespace std;
int n,x[300001],s[300001],c=0;
int main()
{
	memset(x,0,sizeof(x));
	memset(s,0,sizeof(s));
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>x[i]>>s[i];
	}
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	{
		if(x[i]<=x[j]&&s[i]>s[j])
		c++;
	}
	cout<<c<<endl;
}

于是愉快的提交了~~

可是

只有50分

好嘛

我知道暴搜肯定过不了的

我改~~

#include<iostream>
#include<iomanip>
#include<cstring>
using namespace std;
int n,x[300001],s[300001],c=0;
int main()
{
	memset(x,0,sizeof(x));
	memset(s,0,sizeof(s));
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>x[i]>>s[i];
	}
	for(int i=0;i<n-1;i++)
	for(int j=i+1;j<n;j++)
	{
		if(x[i]<=x[j]&&s[i]>s[j])
		c++;
		else if(x[i]>=x[j]&&s[i]<s[j])
		c++;
	}
	cout<<c<<endl;
}

这……

%e6%97%a0%e6%a0%87%e9%a2%98

居然TLE了一半的节点??WTF???

好吧这题怎么写都是50分。这次模拟赛是乐高赛制(提交一次分数打95%),眼看着分就没了,还是不写了……

接着……

洛谷U5874

题目背景

上次老师挑出来的(N-K)位同学很不高兴,于是他们准备自己组建合唱队形。他们请了kkk来帮忙。

题目描述

他们安排了一个动作——手拉着手唱一首歌(就是他们围成一个圈)。如果有两个相邻的同学的身高差非常大(比如姚明和一个1.5米高的人站在一起)的话,评委会感觉非常不爽。于是kkk需要帮助他们求出一种排队方案,使他们身高差距最大值最小,并输出这个最小值和这个方案。

输入输出格式

输入格式:

第一行一个整数N表示有N个人(排成一个圈)

第二行N个整数表示每个人的身高

输出格式:

第一行一个整数表示最小的身高差距最大值

第二行N个整数表示这个最优方案,如果多解输出字典序最小

 

恩这题也是水题嘛(吧)

一般的思路就是把数据排序,然后从中间散开。

但是可能会受到人数是奇数和偶数的影响,所以多个判断~~

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,arr[6001],m[6001],maxn=0;
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	scanf("%d",&arr[i]);
	sort(arr,arr+n);
	if(n%2!=0)
	{
		int half=n/2;
		int a=n-1;
		for(int i=0;i<=n;i++)
		{
			m[half]=arr[a-i];
			if(i%2==0){half+=i+1;}
			else
			half-=i+1;
		}
	}
	if(n%2==0)          //人数根据奇偶不同处理
		{
		int half=n/2;
		int a=n-1;
		for(int i=0;i<n;i++)
		{
			m[half]=arr[a-i];
			if(i%2==0){half+=i+1;}
			else
			half-=i+1;
			if(half==0) {
			m[0]=arr[0]; break;} 
		}
	}
	int ls;
	for(int i=1;i<n;i++)
	{
		ls=m[i]-m[i-1];
		if(ls>maxn) maxn=ls;
	}
	if(fabs(m[n-1]-m[0])>maxn) maxn=fabs(m[n-1]-m[0]);
	printf("%d\n",maxn);
	for(int i=0;i<n;i++)
	{
		if(i!=n-1) printf("%d,",m[i]);
		else printf("%d",m[i]);
	}
	return 0;
}

样例和自己手算的几个数据都通过了~没有满分也该有个4,5个数据点可以过吧。

111

哎呦卧槽这是啥情况啊

坑爹吧这是……

算了,我等苣蒻还是好好的回去学算法吧……

以后再也不出来水题了

(编后语:为了防止误导小盆友,明天会更新标准解法)
11.17更新:似乎今天标准题解还没有放出来orz可能会推迟。

等风来,不如追风去。