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

Re:贪心策略加感性证明

Posted by 15310120844 at 2016-07-06 19:02:48 on Problem 2287
In Reply To:贪心策略加感性证明 Posted by:schnee at 2011-09-16 10:35:21
> /*
> 贪心策略:
> 1,如果田忌的最快马快于齐王的最快马,则两者比。
> (因为若是田忌的别的马很可能就赢不了了,所以两者比)
> 2,如果田忌的最快马慢于齐王的最快马,则用田忌的最慢马和齐王的最快马比。
> (由于所有的马都赢不了齐王的最快马,所以用损失最小的,拿最慢的和他比)
> 3,若相等,则比较田忌的最慢马和齐王的最慢马
> 3.1,若田忌最慢马快于齐王最慢马,两者比。
> (田忌的最慢马既然能赢一个就赢呗,而且齐王的最慢马肯定也得有个和他比,所以选最小的比他快得。)
> 3.2,其他,则拿田忌的最慢马和齐王的最快马比。
> (反正所有的马都比田忌的最慢马快了,所以这匹马必输,选贡献最大的,干掉齐王的最快马)
> 
> 大家想想就明白了应该。
> */
> 
> #include<cstdio>
> #include<cstdlib>
> #include<cstring>
> #include<cmath>
> #include<algorithm>
> using namespace std;
> const int maxn=1005;
> 
> int tj[maxn], qw[maxn];
> 
> int main()
> {
>     int n, i, res, max1, max2, min1, min2, cnt;
>     while(~scanf("%d", &n) && n)
>     {
>         for(i=0; i<n; i++)
>             scanf("%d", &tj[i]);
>         for(i=0; i<n; i++)
>             scanf("%d", &qw[i]);
>         sort(tj, tj+n);
>         sort(qw, qw+n);
> 
>         res=0;
>         max1=max2=n-1;
>         min1=min2=0;
>         cnt=0;
>         while((cnt++)<n)
>         {
>             if(tj[max1]>qw[max2])
>             {
>                 res += 200;
>                 max1--;
>                 max2--;
>             }
>             else if(tj[max1]<qw[max2])
>             {
>                 res -= 200;
>                 min1++;
>                 max2--;
>             }
>             else
>             {
>                 if(tj[min1]>qw[min2])
>                 {
>                     res += 200;
>                     min1++;
>                     min2++;
>                 }
>                 else
>                 {
>                     if(tj[min1]<qw[max2]) res -= 200;
>                     min1++;
>                     max2--;
>                 }
>             }
>         }
>         printf("%d\n", res);
>     }
>     return 0;
> }

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