Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 2085 Inversion---找规律

Posted on 2009-08-26 15:09 Uriel 阅读(499) 评论(0)  编辑 收藏 引用 所属分类: POJ数学
这题丢了很久,一直没什么思路,今天看Discuss说找规律然后就尝试了一下,被绕得有点头晕。。
在网上找了一个解题报告,貌似没考虑 m=0 的情况,但是也可以AC,题目的Bug?
然后理了下思路,一次AC。。考虑了比如(1  0)输出 1  的情况
下面是用来找规律的数据

1 2 3 4 5 6 7 8 9 10   9      0     remain          -  
1 2 3 4 5 6 7 8 10 9   8      1   |    10, 9 
1 2 3 4 5 6 7 9 10 8   7      2   |    9, 10 8 
1 2 3 4 5 6 7 10 9 8   7           |    10, 9 8
1 2 3 4 5 6 8 10 9 7   6      3   |    8, 10 9 7
1 2 3 4 5 6 9 10 8 7   6           |    9, 10 8 7
1 2 3 4 5 6 10 9 8 7   6           |    10, 9 8 7
1 2 3 4 5 7 10 9 8 6   5      4   |    7, 10 9 8 6
1 2 3 4 5 8 10 9 7 6   5           |    8, 10 9 7 6
1 2 3 4 5 9 10 8 7 6   5           |    9, 10 8 7 6
1 2 3 4 5 10 9 8 7 6   5          \|/  10, 9 8 7 6
1 2 3 4 6 10 9 8 7 5   4      5  
1 2 3 4 7 10 9 8 6 5   4
1 2 3 4 8 10 9 7 6 5   4
1 2 3 4 9 10 8 7 6 5   4
1 2 3 4 10 9 8 7 6 5   4
1 2 3 5 10 9 8 7 6 4   3      6
1 2 3 6 10 9 8 7 5 4   3
1 2 3 7 10 9 8 6 5 4   3
1 2 3 8 10 9 7 6 5 4   3
1 2 3 9 10 8 7 6 5 4   3
1 2 3 10 9 8 7 6 5 4   3
1 2 4 10 9 8 7 6 5 3   2      7
1 2 5 10 9 8 7 6 4 3   2
1 2 6 10 9 8 7 5 4 3   2
1 2 7 10 9 8 6 5 4 3   2
1 2 8 10 9 7 6 5 4 3   2
1 2 9 10 8 7 6 5 4 3   2
1 2 10 9 8 7 6 5 4 3   2
1 3 10 9 8 7 6 5 4 2   1      8
1 4 10 9 8 7 6 5 3 2   1
1 5 10 9 8 7 6 4 3 2   1
1 6 10 9 8 7 5 4 3 2   1
1 7 10 9 8 6 5 4 3 2   1
1 8 10 9 7 6 5 4 3 2   1
1 9 10 8 7 6 5 4 3 2   1
1 10 9 8 7 6 5 4 3 2   1
2 10 9 8 7 6 5 4 3 1   0      9
3 10 9 8 7 6 5 4 2 1   0
4 10 9 8 7 6 5 3 2 1   0
5 10 9 8 7 6 4 3 2 1   0
6 10 9 8 7 5 4 3 2 1   0
7 10 9 8 6 5 4 3 2 1   0
8 10 9 7 6 5 4 3 2 1   0
9 10 8 7 6 5 4 3 2 1   0
10 9 8 7 6 5 4 3 2 1   0

下面是AC代码:
/*Problem: 2085  User: Uriel 
   Memory: 384K  Time: 125MS 
   Language: C++  Result: Accepted
*/
 

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

int n,m,i,j,k,flag[50001];

int main()
{
    
while(1)
    
{
        scanf(
"%d %d",&n,&m);
        
if(n==-1 && m==-1)break;
        i
=0;
        memset(flag,
0,sizeof(flag));
        
while((1+(i+1)*i/2)<m)i++;
        
for(j=1;j<=n-i-1;j++)
        
{
            flag[j]
=1;
            printf(
"%d ",j);
        }

        k
=n-i+(m-(i-1)*i/2);
        printf(
"%d ",k);
        flag[k]
=1;
        
for(j=n;j>=1;j--)
        
{
            
if(!flag[j])
            
{
                printf(
"%d ",j);
            }

        }

        printf(
"\n");
    }

    system(
"PAUSE");
    
return 0;
}



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理