编程之美2013初赛——竞价

题目

描述

输入

输出

数据范围

样例输入


2
4 3 5
7 4 7

样例输出
Case #1: 0
Case #2: 1

思路一：

链接地址：http://www.cnblogs.com/chasuner/archive/2013/04/13/3019536.html

这一题想了很久，思路基本都是对的，可惜最后还是放弃了没提交，现在看了别人的代码，理清了一下思路。n是宝石数目，a是Alice的钱币数目，b是bob的钱币数目。

基本就是去找规律，每次要获取宝石，Alice和Bob都必须付出至少1个钱币的代价。获胜的条件是获取超过宝石数目n的一半的宝石（n/2 + 1)，考虑到Alice在最小代价下能获取的宝石数目是a，那么Alice在此时最后到底能否获胜呢？这个取决于n的大小，于是可以根据n的大小分成以下三种情况来考虑：

1.n > 2 * a；即n至少为2 * a + 1。自然会想到比较a和b的大小：

当b > a时，即b至少为a + 1，此时Bob必然获胜，因为即便前面a个宝石全部让给Alice，Bob依然可以获取剩下的至少a+1个宝石；

当b < a时，Alice必然获取，同上，因为即便前面b个宝石全部让给bob，Alice依然可以获取a个宝石，始终比bob的宝石多；

当b = a时，两人买到的宝石一样多。

2.n == 2 * a时，同上考虑：

当b < a时，Alice获胜；

当 b >= 2 * a + 2时，bob获胜，因为想要获胜就必须获取a + 1个宝石，因为Alice有a个宝石，Alice的最优策略是每次至少出1个钱币，所以bob每次必须用2个钱币才能获取一个宝石，所以即b至少为2*（a+1）时bob获胜；

当b >= a && b < 2*a + 2时，两人最终获取的宝石一样多；

3.当n < 2 * a时，此时情况最复杂，我当时就是被这里的细节给吓晕了，根据n的奇偶性分成两种情况：

当n是奇数时，获胜需要的宝石数目是winner = n/2 + 1，因为a > n / 2，所以a的数目至少是等于winner，Alice的想要获胜（即拿到winner个宝石）的最优策略是每次用d = a / winner的钱币来获取一个宝石，bob必胜的情况是每次都付出比Alice的报价多1个(即d + 1个），所以bob至少需要(d + 1) * winner才能保证必胜，所以当b >= (d+1)*winner时，bob必胜；否则的话，Alice必胜。

当n是偶数时，获胜的宝石数目winner2  = n / 2 + 1，平局（即两人拿到的宝石一样多)需要宝石数目是winner1 = n / 2，同样为了拿到winner2个宝石Alice每次付出d2  = a / winner2，为了拿到winner1个宝石Alice每次付出d1 = a / winner1，bob必胜的策略是每次付出（d1 + 1)拿到winner2个宝石，即当b >= (d1+1)*winner2时，bob必胜；Alice必胜的时候则是b< (d2 + 1) * winner1，即bob无法获得至少一半的宝石；当b>= (d2+1) * winner1 && b < (d1+1)*winner2时，两人获取的宝石一样多。

问题分析清楚之后，代码就很好写了，而且小数据和大数据都可以顺利AC!

#include 
  
    using namespace std; int main() { int T; cin >> T; int n, a, b; int k = 0; while(T--) { cin >> n; cin >> a; cin >> b; int result; cout << "Case #"; cout << ++k; cout << ": "; if (n > 2 * a) { if (b > a) result = -1; if (b == a) result = 0; if (b < a) result = 1; cout << result << endl; continue; } if (n == 2 * a) { if (b < a) result = 1; if (b >= a && b <= 2 * a + 1) result = 0; if (b > 2 * a + 1) result = -1; cout << result << endl; continue; } if (n < 2 * a) { if (n % 2 == 0) { int temp1 = n / 2; int temp2 = n / 2 + 1; int d1 = a / temp1; int d2 = a / temp2; int smaller = (d2 + 1) * temp1; int bigger = (d1 + 1) * temp2; if (b < smaller) result = 1; if (b >= bigger) result = -1; if (b >= smaller && b 
   
     = bigger) result = -1; else result = 1; } cout << result << endl; } } return 0; } 
    
  

思路二：

链接地址：http://www.haogongju.net/art/

using namespace std; int judge(int n,int ca,int cb) { int t,va,vb,c; t=(n+1)/2; // 钻石平均分，取上整 vb=cb/t; // 平均分时,Bob每颗钻石所需的单位价值 c=ca/vb; // Alice用这个单位价值能拿多少钻石 if (2*c>n) return 1; t=(n+1)/2; va=ca/t; c=cb/(va+1); // 因为Alice先拿..所以Bob每次总要比Alice多1 if (2&c>n) return -1; return 0; } int main() { int T,t,n,c1,c2,ans; scanf("%d",&T); for (t=1; t<=T; t++) { scanf("%d%d%d",&n,&c1,&c2); printf("Case #%d: %d\n",t,judge(n,c1,c2)); } return 0; }