[河南省ACM省赛-第三届] 房间安排 (nyoj 168)

题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=168

分析:找到一天中需要最多的房间即可

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 200

int day[N];//day[i] 第i天的最多房间数 

int main()
{
    freopen("d:\\in.txt", "r", stdin);
    int t, n;
    scanf("%d", &t);
    while(t--){
        memset(day, , sizeof(day));
        scanf("%d", &n);
        int num, start, length;
        ; i<n; i++){
            scanf("%d%d%d", &num, &start, &length);
            ; i<length; i++){
                day[i+start] += num;
            }
        }
        ;
        ; i<N; i++){
            ans = max(ans, day[i]);
        }
        printf("%d\n", ans);
    } 

    ;
}

看别人题解后才明白的,同时记录下自己的模拟算法(TimeLimitExceeded)

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<string>
 #include<algorithm>
 #include<cmath>
 using namespace std;
 #define INPUT freopen("d:\\in.txt", "r", stdin);
 #define N 10002 

 struct Node {
     int a, b, v;
 }c[N];

 bool cmp(Node n1, Node n2)
 {
     return n1.a != n2.a ? n1.a < n2.a : n1.b < n2.b;
 }
 int main()
 {
     INPUT;

     int t, n;
     scanf("%d", &t);
     while(t--)
     {
         scanf("%d", &n);
         int day;
         ; i<n; i++){
             scanf("%d%d%d", &c[i].v, &c[i].a, &day);
             c[i].b = c[i].a+day;
         }
         sort(c, c+n, cmp);
         ].v;
         ; i<n; i++){
             int cur = c[i].v;
             ans += cur;
             ; j<i; j++){
                 if(c[j].v && cur && c[j].b <= c[i].a){//如果 j团有剩余房间 且 当前订单还需要房间 且j团已离开
                     int reuse = min(c[j].v, cur);
                     ans -= reuse;
                     c[j].v -= reuse;
                     cur -= reuse;
                 }
             }
         }
         printf("%d\n", ans);
     }
     ;
 }
上一篇:我想要得那块牌—记烟台大学第一届"ACM讲堂"


下一篇:ACM、考研、就业,在我心底已经有了明确的答案_人生没有完整的,只有无悔的