uva1612 Guess

和cf的打分有点像啊

因为一共只有三道题，所以每个人的得分最多有8种可能性。把这8种可能性都算出来，存在数组里，排好序备用
排名就是一个天然的链表，给出了扫描的顺序
扫描时，维护两个变量：前一个player的最大得分 recd 和他的ID recdID
扫描到每个player时，从大到小遍历他的8种得分，如果有等于recd的得分，且这个player的ID大于recdID，则只需更新recdID。否则遇到第一个小于recd的得分，就更新recd和recdID。
如果在遍历完8种得分后，还没有满足上面两种情况的，则说明无解

不超过1000，两位小数，可以先*100.0，最后输出/100.0就可以减少误差

tmp_i[j] = (int)(round(tmp_f[j] * 100.0)); //注意转换

位运算： if(j & (1 << k)) 取j从右向左第k+1位

for(int j = 0; j < 8; j++) { //对应3个值取不取的8种情况（111,110,101...）
P[i].score[j] = 0;
for(int k = 0; k < 3; k++)
if(j & (1 << k))
P[i].score[j] += tmp_i[k];
}
sort(P[i].score, P[i].score + 8);

#include<cstdio>

#include<algorithm>

#include<cmath>

const int maxn = ;

using namespace std;

struct player{

    int score[];

}P[maxn];

int nn, ID[maxn];

void read(int n){

        double tmp_f[];

        int tmp_i[];

        for(int i = ; i <= n; i++) {

            scanf("%lf%lf%lf", &tmp_f[], &tmp_f[], &tmp_f[]);

            for(int j = ; j < ; j++)

                tmp_i[j] = (int)(round(tmp_f[j] * 100.0));

            for(int j = ; j < ; j++) {

                P[i].score[j] = ;

                for(int k = ; k < ; k++)

                    if(j & ( << k))

                        P[i].score[j] += tmp_i[k];

            }

            sort(P[i].score, P[i].score + );

        }

}

int main() {

    int kase = ;

    while(scanf("%d", &nn) ==  && nn) {

            read(nn);

        for(int i = ; i <= nn; i++)

            scanf("%d", &ID[i]);

        int MAX = P[ID[]].score[]; //贪心策略

        int pre_ID = ID[], i;

        for(i = ; i <= nn; i++) {

            int cur_ID = ID[i];

            bool flag = false;

            for(int j = ; j >= ; j--) {

                if(P[cur_ID].score[j]  == MAX  && cur_ID > pre_ID) {

                    flag = true;

                    pre_ID = cur_ID;

                    break;

                }

                if(P[cur_ID].score[j] < MAX) {

                    flag = true;

                    pre_ID = cur_ID;

                    MAX = P[cur_ID].score[j];

                    break;

                }

            }

           if(!flag)

               break;

        }

        printf("Case %d: ", kase++);

        if(i != nn + )

            printf("No solution\n");

        else

            printf("%.2lf\n", MAX / 100.0);

    }

    return ;

}

巴特西

uva1612 Guess

最新文章

热门文章