2012年5月14日

还是POJ3984__BFS【四种记录路径的方法总结】

方法一就上一篇最原始的stack保护路径,方法二,三,四(其实一样)是递归回溯深搜路径,只不过存储结构不同,有的很妙,自己的很糟TAT。
后篇将有深搜方法和不用STL做出的。  1 #include<iostream>
  2 #include<queue>
  3 #include<stack>
  4 using namespace std;
  5 //===================================================================
  6 int maze[5][5];
  7 bool mark[5][5];
  8 struct Point 
  9 {
 10     int x,y;
 11 };
 12 
 13 int dir[4][2]={0,1,0,-1,1,0,-1,0};
 14 Point dis[5][5];
 15 stack<Point> S;
 16 int map[5][5];//第三种记录方法
 17 //=====================================================================
 18 
 19 bool InMap(int i,int j)
 20 {
 21     if(i>=0&& i<=4 && j>=0 && j<=4) return true;
 22     else return  false;
 23 }
 24 
 25 void func(int i, int j)
 26 {
 27     if(i==0 && j==0)
 28     {
 29          printf("(0, 0)\n");
 30          return ;
 31     }
 32     Point t;
 33     t.x=i;
 34     t.y=j;
 35     S.push(t);
 36     func(dis[i][j].x,dis[i][j].y);    //递归放入栈,不知道怎么倒序输出
 37 
 38 }
 39 
 40 /*方法二===================================================*/
 41 //void dfs(int x,int y)
 42 //{
 43 //    int pre_x=dis[x][y].x;
 44 //    int pre_y=dis[x][y].y;
 45 //    //如果有祖先,则搜索祖先
 46 //    if(pre_x!=-1 && pre_y!=-1)
 47 //        dfs(pre_x,pre_y);
 48 //    //输出自己的地址,无论是否有祖先(队列中无祖先的只有【0】【0】点)
 49 //    printf("(%d, %d)\n",x,y);
 50 //}
 51 
 52 /*方法三===================================================*/
 53 //void print(int i,int j)
 54 //{
 55 //   if(i==0 && j==0)
 56 //   {
 57 //       printf("(0, 0)\n");
 58 //       return ;
 59 //   }
 60 //
 61 //   print(map[i][j]/5,map[i][j]%5);//先遍历祖先
 62 //   printf("(%d, %d)\n",i,j);
 63 //}
 64 
 65 /*方法四===================================================*/
 66 void print(int i,int j)
 67 {
 68    if(i==0 && j==0)
 69    {
 70        printf("(0, 0)\n");
 71        return ;
 72    }
 73 
 74    print(dis[i][j].x,dis[i][j].y);//先遍历祖先,这两句话的位置很重要,先到祖先,在写自己(下一句话),第一次的错误就是两句话反了
 75     //导致顺序颠倒了
 76    printf("(%d, %d)\n",i,j); 
 77 }
 78 
 79 
 80 void BFS()
 81 {
 82     queue<Point> Q;
 83 
 84     Point cur,m,q;
 85     cur.x=0;
 86     cur.y=0;
 87     mark[0][0]=1;
 88     Q.push(cur);
 89     dis[0][0].x=0;
 90     dis[0][0].y=0;
 91     int xt,yt;
 92 
 93     while(!Q.empty())
 94     {
 95         m=Q.front();
 96         Q.pop();
 97 
 98         for(int i=0;i<4;i++)
 99         {
100             xt=m.x+dir[i][0];
101             yt=m.y+dir[i][1];
102             if(xt==4 && yt==4) 
103             {
104                // func(m.x,m.y);//方法一:放入栈
105                 //dfs(m.x,m.y);//方法二:用深搜
106                 //map[xt][yt]=m.x*5+m.y;//方法三: 用横竖法(自己起的名字),来记录上一次的位置
107                 dis[4][4].x=m.x;
108                 dis[4][4].y=m.y;
109                 print(4,4);
110                 return ;
111             }
112             if(InMap(xt,yt) && mark[xt][yt]==0 && maze[xt][yt]==0)//判断下面一层的结点是否符合
113             {
114 
115                 dis[xt][yt].x=m.x;//记录每上次的结点,这样才可以把整个拎起来
116                 dis[xt][yt].y=m.y;//用dis[][]点来记录每个节点的父节点,因为遍历过就会mark=1,所以只会有一个父节,不会被覆盖
117 
118                 //map[xt][yt]=m.x*5+m.y;//记录路径的好方法!!记录前驱
119 
120                 mark[xt][yt]=1;//访问过后
121                 q.x=xt;
122                 q.y=yt;
123                 Q.push(q);
124 
125             }
126         }
127     }
128 }
129 
130 
131 
132 int main()
133 {
134     int i,j;
135 
136     freopen("in.txt","r",stdin);
137     for(i=0;i<5;i++)
138         for(j=0;j<5;j++)
139             scanf("%d",&maze[i][j]);
140 
141     BFS();
142 
143     //print(4,4);
144     //while(!S.empty())//打印路径
145     //{
146     //    printf("(%d, %d)\n",S.top().x,S.top().y);
147     //    S.pop();
148     //}
149     //printf("(4, 4)\n");
150 
151 
152 
153 
154 
155 
156 }

posted @ 2012-05-14 23:45 四也 阅读(489) | 评论 (0)编辑 收藏

POJ 3984 方法一【BFS+Stack 记录路径】

刚学搜索,总是不开窍,看了介绍,自己磨了两小时才写出来。后面会有DFS和改进后的方法。想通过这道水题,把搜索入了门先。
蓝桥大赛还有几天,再看看,自己水死了。
自己的代码:  1 #include<iostream>
  2 #include<queue>
  3 #include<stack>
  4 using namespace std;
  5 //===================================================================
  6 int maze[5][5];
  7 bool mark[5][5];
  8 struct Point 
  9 {
 10     int x,y;
 11 };
 12 
 13 int dir[4][2]={0,1,0,-1,1,0,-1,0};
 14 Point dis[5][5];
 15 stack<Point> S;
 16 int map[5][5];
 17 //=====================================================================
 18 
 19 bool InMap(int i,int j)
 20 {
 21     if(i>=0&& i<=4 && j>=0 && j<=4) return true;
 22     else return  false;
 23 }
 24 
 25 void func(int i, int j)
 26 {
 27     if(i==0 && j==0)
 28     {
 29          printf("(0, 0)\n");
 30          return ;
 31     }
 32     Point t;
 33     t.x=i;
 34     t.y=j;
 35     S.push(t);
 36     func(dis[i][j].x,dis[i][j].y);    //递归放入栈,不知道怎么倒序输出
 37 
 38 }
 39 
 40 void BFS()
 41 {
 42     queue<Point> Q;
 43 
 44     Point cur,m,q;
 45     cur.x=0;
 46     cur.y=0;
 47     mark[0][0]=1;
 48     Q.push(cur);
 49     dis[0][0].x=0;
 50     dis[0][0].y=0;
 51     int xt,yt;
 52 
 53     while(!Q.empty())
 54     {
 55         m=Q.front();
 56         Q.pop();
 57 
 58         for(int i=0;i<4;i++)
 59         {
 60             xt=m.x+dir[i][0];
 61             yt=m.y+dir[i][1];
 62             if(xt==4 && yt==4) 
 63             {
 64                 func(m.x,m.y);//放入栈
 65                 return ;
 66             }
 67             if(InMap(xt,yt) && mark[xt][yt]==0 && maze[xt][yt]==0)//判断下面一层的结点是否符合
 68             {
 69 
 70                 dis[xt][yt].x=m.x;//记录每上次的结点,这样才可以把整个拎起来
 71                 dis[xt][yt].y=m.y;//用dis[][]点来记录每个节点的父节点,因为遍历过就会mark=1,所以只会有一个父节,不会被覆盖
 72                 mark[xt][yt]=1;//访问过后
 73                 q.x=xt;
 74                 q.y=yt;
 75                 Q.push(q);
 76 
 77             }
 78         }
 79     }
 80 }
 81 
 82 int main()
 83 {
 84     int i,j;
 85 
 86     //freopen("in.txt","r",stdin);
 87     for(i=0;i<5;i++)
 88         for(j=0;j<5;j++)
 89             scanf("%d",&maze[i][j]);
 90 
 91     BFS();
 92 
 93     while(!S.empty())//打印路径
 94     {
 95         printf("(%d, %d)\n",S.top().x,S.top().y);
 96         S.pop();
 97     }
 98     printf("(4, 4)\n");
 99 
100 
101 
102 
103 
104 
105 }

posted @ 2012-05-14 23:02 四也 阅读(346) | 评论 (0)编辑 收藏

2012年5月6日

【算法导论】动态规划实现

对于 line[6][2]的记录机制还有疑问,等下细细看来,再补上解答 1 #include<iostream>
 2 using namespace std;
 3 //==========================================================================
 4 int a[2][100];
 5 int f[2][100];
 6 int t[2][100];
 7 int line[2][100];
 8 int e[2];
 9 int x[2];
10 int lend,fend;
11 //==========================================================================
12 void  FastWay(int a[2][6],int t[2][5],int e[2],int x[2],int n,int &fend,int &lend)
13 {
14      f[0][0] = e[0] + a[0][0];
15     f[1][0] = e[1] + a[1][0];
16     cout << a[0][1] << endl;
17     cout << a[1][1] << endl;
18     for (int j = 1; j < n; j++)
19     {
20         if (f[0][j-1] + a[0][j] <= f[1][j-1] + t[1][j-1] + a[0][j])
21         {
22             f[0][j] = f[0][j-1] + a[0][j];
23             line[0][j] = 0;
24         }
25         else
26         {
27             f[0][j] = f[1][j-1] + t[1][j-1] + a[0][j];
28             line[0][j] = 1;
29         }
30         if (f[1][j-1] + a[1][j] <= f[0][j-1] + t[0][j-1] + a[1][j])
31         {
32             f[1][j] = f[1][j-1] + a[1][j];
33             line[1][j] = 1;
34         }
35         else
36         {
37             f[1][j] = f[0][j-1] + t[0][j-1] + a[1][j];
38             line[1][j] = 0;
39         }
40     }
41     if (f[0][n-1] + x[0] <= f[1][n-1] + x[1])
42     {
43         fend = f[0][n-1] + x[0];
44         lend = 0;
45     }
46     else
47     {
48         fend = f[1][n-1] + x[1];
49         lend = 1;
50     }
51 
52 }
53 
54 //===============================================================================================
55 void PrintStations(int line[2][6],int lend, int n)
56 {
57     int i=lend;
58     cout<<"Line "<<i<<" Station "<<n<<endl; 
59     for(int j=n-1;j>=2;j--)
60     {
61         i=line[i][j];//?????????????????/
62         cout<<"Line "<<i<<" Station "<<j-1<<endl; 
63     }
64 }
65 //===============================================================================================
66 int main()
67 {
68     int n=6;
69     int e[3]={2,4};
70     int x[3]={3,2};
71     int a[2][6]={7,9,3,4,8,4,8,5,6,4,5,7};
72     int t[2][5]={2,3,1,3,4,2,1,2,2,1};
73 
74     int Line[2][6];
75     int LastFlag;
76     int fend;
77 
78      FastWay(a, t, e, x, n,fend,LastFlag);
79     printf("fast = %d;\n", fend);
80     
81     PrintStations(Line, LastFlag, n);
82     return 0;
83 
84 }

posted @ 2012-05-06 21:15 四也 阅读(95) | 评论 (0)编辑 收藏

2011年11月29日

POJ 1050 二维最大子矩阵

 1 //解法一:自己的解法:先求每一行中从i到j的和存储在sum[r]中r从1到n,记录每一列从i到j的和。然后用
 2 //    一维数组的方法求出。47MS。
 3 #include<iostream>
 4 using namespace std;
 5 //=============================================
 6 #define N 102
 7 int p[N][N];
 8 int b[N][N];
 9 #define M 128;
10 int sum[N];
11 //==============================================
12 int Maxtri(int start,int end,int *a)//一维数组求最大子段和
13 {
14     int s=0;int max=-M;
15     for(int i=start;i<=end;++i)
16     {
17         if(s+a[i]>0)
18         {
19             s=s+a[i];
20         }
21         else
22         {
23             s=0;
24         }
25         if(s>max)max=s;
26     }
27     return max;
28 }
29 
30 int main()
31 {
32     int n;
33     int m=-M;
34     cin>>n;
35     for(int i=1;i<=n;++i)
36     {
37         for(int j=1;j<=n;++j)
38         {
39             cin>>p[i][j];
40         }
41     }
42     for(int i=1;i<=n;++i)
43     {
44         for(int j=i;j<=n;++j)
45         {
46             for(int r=1;r<=n;++r)
47             {
48                 sum[r]=0;//勿忘,每次都初始化。。。
49                 for(int k=i;k<=j;++k)
50                 {
51                     sum[r]+=p[r][k];
52                 }
53             }
54             if(Maxtri(1,n,sum)>m)m=Maxtri(1,n,sum);
55         }
56     }
57     cout<<m<<endl;
58 }
59 

posted @ 2011-11-29 20:42 四也 阅读(199) | 评论 (0)编辑 收藏

2011年11月28日

POJ 2479 最大子段和 问题

  1 /*最大子序和问题,从左到右和从右到左用了不同的方法
  2 求从右到左时我用了
  3     for(int i=0;i<n;++i)
  4     {
  5         if(b+p[i]>0)
  6         {
  7             b=b+p[i];
  8         }
  9         else
 10         {
 11             b=0;
 12         }
 13         if(b>max)max=b;
 14     }
 15     cout<<max<<endl;
 16 这个方法。而从右到左求时,用这方法时
 17 如下
 18         sum2[n-1]=0;
 19         for(int i=n-1;i>=1;--i)
 20        {
 21            if(sum2[i+1]+p[i]>0)
 22            {
 23                sum2[i]=sum2[i+1]+p[i];
 24            }
 25            else
 26            {
 27                sum2[i]=0;
 28            }
 29            if(sum2[i]>max)max=sum2[i];
 30            一直W。。TAT.不知为何.所以换了个方法如下。
 31 主要思路:两个不相交字串,一个从左到右求出sum1[i]为右边前i个数中最大字串(未必从第一个开始,也未必最后一个结束,的任意子串),
 32 而从这时的i到n中求出最大子串值和其相加时,未必为最大和。所以先保证从右到左为最大,求出i,再从i到1求出。
 33 再从和中挑出最大的,若两个都挑出最大的,用函数的话会超时很惨的。*/
 34 
 35 #include<iostream>
 36 #include<stdio.h>
 37 using namespace std;
 38 //=====================================================
 39 #define M 50001
 40 int k;
 41 int p[M],sum1[M],sum2[M];
 42 //=====================================================
 43 int main()
 44 {
 45     int n;
 46     int max=-M;
 47     // freopen( "in.txt", "r", stdin);
 48     //freopen( "out.txt", "w+", stdout); 
 49    scanf("%d",&k);
 50    while(k--)
 51    {
 52        int n;
 53        scanf("%d",&n);
 54 
 55        int max=-M;
 56        int m=-M;
 57        scanf("%d",&p[0]);
 58      
 59       sum1[0]=p[0];
 60     
 61 
 62       for(int i=1;i<n;++i)
 63       {
 64            scanf("%d",&p[i]);
 65            if(sum1[i-1]+p[i]>0)
 66            {
 67                sum1[i]=sum1[i-1]+p[i];
 68            }
 69            else
 70            {
 71                sum1[i]=0;
 72            }
 73        }
 74        sum2[n-1]=p[n-1];
 75        for(int i=n-1;i>=1;--i)
 76        {
 77            if(sum2[i]>0)
 78            {
 79                sum2[i-1]=sum2[i]+p[i-1];
 80            }
 81            else
 82            {
 83                sum2[i-1]=p[i-1];
 84            }
 85            if(sum2[i]>max)max=sum2[i];
 86 
 87            if(sum1[i-1]+max>m)
 88            {
 89                m=sum1[i-1]+max;
 90            }
 91         }
 92         printf("%d\n",m);
 93    }
 94 }
 95      
 96        
 97 
 98 
 99 
100 
101      
102        
103 
104 

posted @ 2011-11-28 22:37 四也 阅读(144) | 评论 (0)编辑 收藏

2011年11月27日

POJ 1458 最长公共子列

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 //================================================
 5 string str1,str2;
 6 int c[1000][1000];//c[i][j]表示到x中的第i个和y中的第j个的已有最长字串的长度
 7 int max(int a,int b)
 8 {
 9     return (a>b?a:b);
10 }
11 int main()
12 {
13     while(cin>>str1>>str2)
14     {
15        //int counter=0;二货!!!!!!!!!!!
16         memset(c,0,sizeof(c));
17         int s1=str1.size();
18         int s2=str2.size();
19         //for(int i=0;i<s1;++i) c[i][0]=0;二货!!字符串时str[0]也是有用的!!
20         //for(int j=0;j<s2;++j) c[0][j]=0;
21         for(int i=1;i<=s1;++i)
22         {
23             for(int j=1;j<=s2;++j)
24             {
25                 if(str1[i-1]==str2[j-1])//处理字符串时又不能从一开始的时候,可以在判断的时候迂回一下
26                 {
27                     c[i][j]=c[i-1][j-1]+1;//通过上一个表示自己,i和j在c[i][j]表示个数时都为加一以后所负责表示。
28                 }
29                 else
30                 {
31                     c[i][j]=max(c[i-1][j],c[i][j-1]);
32                 }
33             }
34         
35         }
36        cout<<c[s1][s2]<<endl;//通过最后递推结果来说明。
37     }
38 }
39 

posted @ 2011-11-27 16:34 四也 阅读(101) | 评论 (0)编辑 收藏

POJ 3070 这个为矩阵相乘的基础题。

建议做矩阵相乘时先做3070,后面在开始做3233,3623,2440.3623和2440我还没开始做,今天下午就要自己做出来!!!!还有。。。海贼王更新了!!!!
 1 #include<iostream>
 2 using namespace std;
 3 //===================================================
 4 int k;
 5 struct Point 
 6 {
 7     int a[2][2];
 8     void init()
 9     {
10         a[0][0]=1;a[0][1]=1;
11         a[1][0]=1;a[1][1]=0;
12     }
13 };
14 
15 Point mul(Point p,Point q)//矩阵相乘
16 {
17     int i,j;
18     Point c;
19     for(i=0;i<2;++i)
20     {
21         for(int j=0;j<2;++j)
22         {
23             int sum=0;
24             for(int k=0;k<2;++k)
25             {
26                 sum+=(p.a[i][k]*q.a[k][j])%10000;
27             /*    if(sum>10000)
28                 {
29                     sum-=10000;
30                 }*/
31                 c.a[i][j]=sum%10000;
32             }
33         }
34      }
35     return c;
36 }
37 
38 Point maxtrimul(Point s,int k)
39 {
40     Point ans;
41     ans=s;
42     if(k==1)return s;
43     ans=maxtrimul(s,k>>1);
44     ans=mul(ans,ans);
45     if(k&1)
46     {
47         ans=mul(s,ans);//切记!!!!
48     }
49     return ans;
50     
51 
52 }
53 
54 int main()
55 {
56     Point s;
57     s.init();
58     Point c;
59     while(cin>>k&&k!=-1)
60     {
61         if(k==0)
62         {
63             cout<<0<<endl;
64             continue;
65         }
66         if(k==1)
67         {
68             cout<<1<<endl;
69             continue;
70         }
71         c=maxtrimul(s,k);
72         cout<<(c.a[0][1]%10000)<<endl;
73         continue;
74 
75     }
76 }

posted @ 2011-11-27 11:54 四也 阅读(124) | 评论 (0)编辑 收藏

POJ 3233 快速幂和二分。。。基本上是别人的代码,自己改动一些,不过收获很大。

借鉴http://www.cnblogs.com/ACShiryu/archive/2011/08/09/poj3233.html
  1  /* 这道题目借鉴他人的思路和代码,很有收获
  2   先看下面这个快速幂求余的运算
  3 递归用二分法,每个过程都求余。
  4 long exp_mod(long a,long n,long b)
  5 {
  6     long t;
  7     if(n==0) return 1%b;
  8     if(n==1) return a%b;
  9     t=exp_mod(a,n/2,b);
 10     t=t*t%b;
 11     if((n&1)==1) t=t*a%b;
 12     return t;
 13 }
 14 本题用了两次二分的思想,一次用于求A^K,第二次用于求 (1+A^(k/2))*(A + A^2 + A^3 + … + A^(k/2))
 15 */
 16 
 17 
 18 #include<iostream>
 19 #include<stdio.h>
 20 using namespace std;
 21 //=======================================================
 22 int n,m,k;
 23 struct Point//定义结构体更加方便,用数组时结构体有大作用的
 24 {
 25      int a[32][32];
 26      void init()
 27      {
 28          memset(a,0,sizeof(a));
 29          for(int i=1;i<=32;++i)
 30          {
 31              a[i][i]=1;
 32          }
 33      }
 34 };
 35 //=======================================================
 36 Point mul(Point x,Point y)//乘法运算
 37 {
 38     Point z;
 39     for(int i=1;i<=n;++i)
 40     {
 41         for(int j=1;j<=n;++j)
 42         {
 43             int sum=0;
 44             for(int k=1;k<=n;++k)
 45             {
 46                 sum+=((x.a[i][k]*y.a[k][j])%m);//每次都求余
 47                 z.a[i][j]=(sum%m);//这时也要求余。。。。。。
 48             }
 49         }
 50     }
 51     return z;
 52 }
 53 
 54 Point add(Point p,Point q)//矩阵加法运算
 55 {
 56     Point c;
 57     for(int i=1;i<=n;++i)
 58     {
 59         for(int j=1;j<=n;++j)
 60         {
 61             c.a[i][j]=((p.a[i][j]+q.a[i][j])%m);//记得求余
 62         }
 63     }
 64     return c;
 65 }
 66 
 67 void display(Point p)//打印函数
 68 {
 69     int i,j;
 70     for( i=1;i<=n;++i)
 71     {
 72         for(j=1;j<=n-1;++j)
 73         {
 74             cout<<p.a[i][j]<<" ";//注意格式“ ”问题
 75         }
 76         if(j==n)cout<<p.a[i][j]<<endl;
 77         
 78     }
 79 }
 80 
 81 Point maxtrimul(Point s,int k)//用递归定义实现快速幂的乘法
 82 {
 83     Point ans;//用来存放结果的
 84     ans.init();
 85     if(k==1)return s;
 86     ans=maxtrimul(s,k>>1);//每次二分
 87     ans=mul(ans,ans);
 88     if(k&1//奇数时再乘一次
 89     {
 90         ans=mul(s,ans);
 91     }
 92     return ans;
 93   
 94 }
 95 
 96 Point maxtrisum(Point s,int k)
 97 {
 98     if(k==1)return s;
 99        Point ans;//用来保存答案
100     ans.init();
101     ans=add(ans,maxtrimul(s,k>>1));
102     ans=mul(ans,maxtrisum(s,k>>1));
103     if(k&1)//奇数时
104     {
105         ans=add(ans,maxtrimul(s,k));
106     }
107     return ans;
108 
109 }
110 
111 int main()                                                                                                                                                                                                     
112 {
113     cin>>n>>k>>m;
114     Point s;
115     for(int i=1;i<=n;++i)
116     {
117         for(int j=1;j<=n;++j)
118         {
119             cin>>s.a[i][j];
120         }
121     }
122     s=maxtrisum(s,k);
123     display(s);
124  
125 }
126 

posted @ 2011-11-27 10:58 四也 阅读(66) | 评论 (0)编辑 收藏

2011年11月24日

POJ 1828

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 //======================================================
 5 struct Point
 6 {
 7     int x;int y;
 8     int flag;
 9 };
10 struct Point p[50050];
11 int n;
12 //======================================================
13 //原来自己用了两方面即想x相同时比y,y相同时比x,两个排序,两个比较,超时。没有下面方法好,只用了一半。。。要好好加油了~TVT.
14 //按照x从小到大排序,当x相等时按照y从大到小排序,从左到右,见到最高的就加一,counter初始值为1
15 //即x最大时,y中也是最大值的p[n-1].y一定是,然后就像爬楼梯一样比较
16 int cmp1( const void *a , const void *b )
17 {
18     struct Point *= (Point *)a;
19     struct Point *= (Point *)b;
20     if(c->!= d->x) return c->- d->x;
21     else return c->- d->y;
22 }
23 
24 
25 //==============================================================
26 int main()
27 {
28 
29     while(scanf("%d",&n)!=EOF&&n)
30     {
31         int counter=1;
32         memset(p,0,sizeof(p));
33         for(int i=0;i<n;++i)
34         {
35             cin>>p[i].x>>p[i].y;
36         }
37         qsort(p,n,sizeof(p[0]),cmp1);//按照x从小到大排序,当x相等时按照y从大到小排序
38         //从左到右,见到最高的就加一
39         int max=p[n-1].y;
40         for(int i=n-2;i>=0;--i)
41         {
42             if(p[i].y>max)
43             {
44                 counter++;
45                 max=p[i].y;
46             }
47         }
48         printf("%d\n",counter);
49     }
50     
51 }

posted @ 2011-11-24 11:39 四也 阅读(165) | 评论 (0)编辑 收藏

2011年11月22日

POJ 1723

我真是太菜了。。。看了N个别人的解答,就是不懂。。直到这个出现,我终于懂了一点。。。。
首先考虑纵坐标:
对纵坐标做一次排序,那么,只要最终选择的纵坐标不小于最小的,且不大于最大的,那么对于一头一尾两个点,效果都是相同的;依此类推,所以,选择的纵坐标就是整个纵坐标序列的中位数了,简单吧?
再来考虑横坐标:
还是进行一次升序排列,很显然,这就是最终的顺序了(否则肯定会浪费移动次数),即:
X1 -> X0
X2 -> X0 + 1
...
Xn -> X0 + n - 1
也就是:
X1 -> X0
X2 - 1 -> X0
...

Xn - (n - 1) -> X0  //
来自http://blog.sina.com.cn/s/blog_67ac571c0100itfv.html
下面是我自己的的代码了TVT~
 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 using namespace std;
 5 //========================================
 6 int x[10010];
 7 int y[10010];
 8 int main()
 9 {
10     int n;
11     cin>>n;
12     int counts=0;
13     for(int i=0;i<n;++i)
14     {
15         cin>>x[i]>>y[i];
16     }
17     sort(y,y+n);
18     sort(x,x+n);
19     int yz=y[n/2];
20     for(int i=0;i<n;++i)
21     {
22         x[i]=x[i]-i;
23     }
24     sort(x,x+n);
25     int xz=x[n/2];
26     for(int i=0;i<n;++i)
27     {
28         counts+=(abs(y[i]-yz)+abs(x[i]-xz));
29     }
30     cout<<counts<<endl;
31 
32     
33 
34 }




posted @ 2011-11-22 21:24 四也 阅读(218) | 评论 (0)编辑 收藏

仅列出标题  下一页
<2019年2月>
272829303112
3456789
10111213141516
17181920212223
242526272812
3456789

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜