关于poj1883超时的问题

来源:百度知道 编辑:UC知道 时间:2024/05/07 17:25:39
http://hi.baidu.com/dizemmm/blog/item/6f3c27c2d9ffad3de4dd3b76.html
这里有个ac了的代码,我一点也没看出来比我的代码快在那里,但我的代码就是超时,快崩溃了

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int nums[1100];

int compare(const void* elem1,const void* elem2)
{
return (strcmp((char*)elem1,(char*)elem2));
}

int main()
{
int T,n,k,i,j,l,tj;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(i=0;i<n;i++)
scanf("%d",nums+i);
for(i=0;i<k;i++)
{
for(j=n-1;j>0;j--)
{
if(nums[j-1]<nums[j])
{
tj=nums[j-1];
//for(l=(j+n-1)/2;!(nums[l]>tj&&(l==n-1||nums[l+1]<tj));)
for(l=(j+n-1)/2;nums[l]<tj||(l!=n-1&&nums[l+1]>tj);)
{<

我也做了这道题, 正常做法, 1Y

看了你的代码, 二分搜索那里写的好诡异…… 怎么看都觉得有问题

首先 这里不需要二分的…… 因为sort一下是nlogn, 你前面搜索加速了也没多大意义

其次 你的二分真的看着比较有问题…… l=(l+n)/2; l=(l-1+j)/2; 这里容易出错, 万一 l == n 岂不死循环了, 还是规规矩矩的写l r mid 吧…… 说老实话 我看不懂你这个二分……