| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:贪心策略加感性证明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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator