Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

感觉这道题的检测程序有瑕疵,不符合逆序数相同按原来的顺序排序

Posted by degiminnal at 2018-07-29 21:23:48 on Problem 1007
测试数据:
10 7
ATCGATGCAT
GATCAGATTT
CCCGGGGGGA
ATCGATGCBT
AACATAGAGG
TTTTGGCCAA
TTTGGCCAAA

问题阐述:
我写的程序输入上面的数据时会有如下输出,为了方便查看,输出时加上了逆序数:

/***********************WA代码运行结果**********************
CCCGGGGGGA   9
AACATAGAGG   9
GATCAGATTT   11
ATCGATGCAT   17 ...............注意这里
ATCGATGCBT   17
TTTTGGCCAA   36
TTTGGCCAAA   37
很遗憾我的程序提交后显示的WA。
后来我在网上找了一份源码,提交后显示ACCEPT。用那段源码跑同样的数据会出现:

/*******************ACCEPT代码运行结果**********************
CCCGGGGGGA    9
AACATAGAGG    9
GATCAGATTT    11
ATCGATGCBT    17 ...............注意这里
ATCGATGCAT    17
TTTTGGCCAA    36
TTTGGCCAAA    37
可以看到两个程序结果的细微差别。逆序数同为17,两个的顺序发生了反转。
再看最初的输入:
         ATCGATGCAT 在前
         ATCGATGCBT 在后
显而易见,被系统否认的代码是正确的。

附:可能我的考虑不周到,说法有误,请大家指正,希望进一步学习。

    附录有我的WA源码和网上找来的ACCEPT源码

####################################################################
####################################################################
                        
                            附录

我的源代码:

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#define N 150

#define L 52

void main()

{

	int nums, lens;

	char str[N][L];

	int i, j, k;

	char temp[L];

	int res[N];

	memset(res, 0, sizeof(res));

	scanf("%d%d", &lens, &nums);

	for (i = 0; i < nums; i++)

		scanf("%s", str[i]);

	for (i = 0; i < nums; i++)

	{

		for (j = 0; j < lens - 1; j++)

		{

			for (k = j + 1; k < lens; k++)

			{

				if (str[i][k] < str[i][j])

					res[i]++;

			}

		}

	}

	for (i = 0; i < nums - 1; i++)

	{

		k = i;

		for (j = i + 1; j < nums; j++)

		{

			if (res[j] < res[k])

			{

				k = j;

			}

		}

		if (k > i)

		{
			int temp = res[k];

			char tmp[L];

			strcpy(tmp, str[k]);

			for (j = k; j > i; j--)

			{
				res[j] = res[j - 1];

				strcpy(str[j], str[j - 1]);

			}

			res[i] = temp;

			strcpy(str[i], tmp);

		}

	}

	for (i = 0; i < nums; i++)

	{

		printf("%s\n", str[i]);

		//printf("   %d\n", res[i]);

	}

}


#######################################################################
#######################################################################

网上找来的ACCEPT源码:

#define _CRT_SECURE_NO_WARNINGS

#include<cstdio>

#include<stdlib.h>

using namespace std;

struct _stru_DNA

{

	char String[52];

	int Measure;

};

_stru_DNA DNA[110];

int n, m;

//计算第Index条DNA的Measure

void CountMeasure(int Index);

//DNA排序

void SortDNA();



int main(void)

{

	int i;

	scanf("%d%d", &n, &m);

	for (i = 0; i<m; i++)

	{

		scanf("%s", DNA[i].String);

		CountMeasure(i);

		//printf("%d\n", DNA[i].Measure);

	}

	SortDNA();

	for (i = 0; i<m; i++)

	{

		printf("%s    ", DNA[i].String);

		printf("%d\n", DNA[i].Measure);

	}

	system("pause");

	return 0;

}

//计算第Index条DNA的Measure

void CountMeasure(int Index)

{

	int i, j;

	int Measure = 0;

	for (i = 0; i<n - 1; i++)

	{

		if ('A' == DNA[Index].String[i])

		{

			continue;

		}

		for (j = i + 1; j<n; j++)

		{

			if (DNA[Index].String[i] > DNA[Index].String[j])

			{

				Measure++;

			}

		}

	}

	DNA[Index].Measure = Measure;

}

//DNA排序

void SortDNA()

{

	int i, j;

	int MinIndex;

	_stru_DNA Tmp;

	for (i = 0; i<m - 1; i++)

	{

		MinIndex = i;

		for (j = i + 1; j<m; j++)

		{

			if (DNA[j].Measure < DNA[MinIndex].Measure)

			{

				MinIndex = j;

			}

		}

		Tmp = DNA[i];

		DNA[i] = DNA[MinIndex];

		DNA[MinIndex] = Tmp;

	}

}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator