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