Codeforces Round #100(140~~)

题目大意：有一个大圆桌子，半径是R，然后有n个半径是r的盘子，现在需要把这些盘子摆放在桌子上，并且只能摆放在桌子边缘，但是不能超出桌子的范围....问能放摆放下。

分析：先求出如果可以摆放n个盘子的最大夹角a，然后计算出来两个圆之间的距离，就可以判断出来是否能摆放下，注意1的时候需要特殊判断。

#include<stdio.h>
#include<math.h>

const double PI = acos(-1.0);
const double EPS = 1e-10;

int Sign(double x)
{
    if(x > EPS)return 1;
    if(fabs(x) < EPS)return 0;
    return -1;
}

int main()
{
    int n, R, r;

    scanf("%d%d%d", &n, &R, &r);

    double a = PI / (n*1.0);
    double L = R-r;

    int k = Sign((sin(a)*L)-r*1.0);

    if((n == 1 && r <= R) || (n != 1 && k>=0) )
        printf("YES
");
    else
        printf("NO
");

    return 0;
}

View Code

140 B. New Year Cards

题目大意：这个叫亚历山大的男子有n个朋友，他的这n个朋友编号从 1到n，然后时间 i（1<=i<=n）的时候他的朋友 i 给他发送贺卡 i....当然收到贺卡就需要回复，他本来没有贺卡，不过他回复遵循两个原则，1.他不会把一个朋友发给他的贺卡再给他这个朋友发过去。 2.他会从已有的贺卡里面选出一张他最喜欢的发送给他的朋友。他可以选择任意时间给每个朋友发送贺卡，当然他也希望最大满足朋友的喜好，所以会尽量发别人喜欢的贺卡，求出来给每个人发送贺卡的时间点。

分析：因为要求的是什么时候发送，而且要最大满足喜好，所以可以从每个人喜欢的贺卡开始判断，这个贺卡能不能被发出，被发出判断的条件很明显是前面没有比它小的值，或者有一个比它小的值并且这个值就是这个人（这样就会满足第一个条件），预处理一下就行了。

#include<stdio.h>
#include<math.h>

const int MAXN = 307;

int like[MAXN][MAXN];

int main()
{
    int N, index[MAXN];

    scanf("%d", &N);

    for(int i=1; i<=N; i++)
    for(int j=1; j<=N; j++)
        scanf("%d", &like[i][j]);

    for(int i=1; i<=N; i++)
    {
        scanf("%d", &like[0][i]);
        index[like[0][i]] = i;
    }

    int Time[MAXN], send[MAXN]={0};
    ///send[]-1表示这个不可能发送，有数字表示这个只能发送给他
    ///send[]等于0表示这个人可以接收这个卡
    for(int i=1; i<=N; i++)
    for(int j=1; j<i; j++)
    {
        if(like[0][i] > like[0][j])
        {
            if(send[i] == 0)
                send[i] = like[0][j];
            else
            {
                send[i] = -1;
                break;
            }
        }
    }

    for(int i=1; i<=N; i++)
    for(int j=1; j<=N; j++)
    {
        if(like[i][j] == i)
            continue;

        int k = index[like[i][j]];

        if(!send[k] || send[k] == i)
        {
            Time[i] = like[i][j];
            break;
        }
    }

    for(int i=1; i<=N; i++)
        printf("%d%c", Time[i], i==N?'
':' ');

    return 0;
}

View Code

140 C. New Year Snowmen

题目大意：有n个不同半径的雪球，堆雪人需要三个不同半径的雪球，求出来最多能堆几个雪人。。。并且输出每个雪人的雪球大小（降序）

分析：因为给的半径比较大，所以先进行一下离散化，求出来每种半径的雪球有多少个，然后维护一个优先队列，每次都取最多的三个雪球，直到队列里面的数小于3.

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;

const int MAXN = 1e5+7;

int Hash[MAXN], r[MAXN];
int sum[MAXN];

struct Radii
{
    int id, cnt;
    bool operator < (const Radii &t)const{
        return cnt < t.cnt;
    }
};

int ans[MAXN][3];

int main()
{
    int N, M, k=0;

    scanf("%d", &N);

    for(int i=0; i<N; i++)
    {
        scanf("%d", &r[i]);
        Hash[i] = r[i];
    }

    sort(Hash, Hash+N);
    M = unique(Hash, Hash+N) - Hash;

    memset(sum, 0, sizeof(sum));

    for(int i=0; i<N; i++)
    {
        int id = lower_bound(Hash, Hash+M, r[i]) - Hash;
        sum[id]++;
    }

    priority_queue<Radii> Q;
    Radii p;

    for(int i=0; i<M; i++)
    {
        if(sum[i])
        {
            p.id = i;
            p.cnt = sum[i];
            Q.push(p);
        }
    }

    Radii Out[10];

    while(Q.size() > 2)
    {
        for(int i=0; i<3; i++)
        {
            Out[i] = Q.top();
            Q.pop();
            ans[k][i] = Hash[Out[i].id];
            Out[i].cnt -= 1;
        }
        for(int i=0; i<3; i++)
        {
            if(Out[i].cnt)
                Q.push(Out[i]);
        }
        k++;
    }

    printf("%d
", k);

    for(int i=0; i<k; i++)
    {
        sort(ans[i], ans[i]+3);
        printf("%d %d %d
", ans[i][2], ans[i][1], ans[i][0]);
    }

    return 0;
}

View Code

140 D. New Year Contest

题目大意：有一个比赛，比赛时间从18:00 - 6:00 比赛前10分钟思考策略，不进行答题，他计算出解决每个问题需要的时间，不过这个罚时比较特殊，罚时为提交的时间到达24:00的时间，不过做题可以解决好先不提交，提交不占时间，求出来去多解决多少问题，并且最少的罚时是多少。

分析：比较容易的贪心，先从小到达进行排序，然后取就行了。。。顺便记录罚时。。。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;

const int MAXN = 107;

int main()
{
    int N, time[MAXN];

    scanf("%d", &N);

    for(int i=0; i<N; i++)
        scanf("%d", &time[i]);
    sort(time, time+N);

    int i, sum=10, pen=0;

    for(i=0; i<N; i++)
    {
        if(sum + time[i] <= 360)
            sum += time[i];
        else if(sum+time[i] > 360 && sum+time[i] <= 720)
        {
            sum += time[i];
            pen += sum - 360;
        }
        else if(sum + time[i] > 720)
            break;
    }

    printf("%d %d
", i, pen);

    return 0;
}

View Code