Poj在線評測平臺，POJ 3988 Selecting courses

2023-11-09 阅读 26 评论 0

摘要：題目鏈接：http://poj.org/problem?id=3988 題意：每種課都有自己的開始開始和結束時間，學生任選一時間點開始選課，一旦開始每5分鐘只能選且必選(如果可以)一次。求學生能選到的最多的課數。分析：因為一開始沒仔細看題，沒注意到

題目鏈接：http://poj.org/problem?id=3988

題意：每種課都有自己的開始開始和結束時間，學生任選一時間點開始選課，一旦開始每5分鐘只能選且必選(如果可以)一次。求學生能選到的最多的課數。

分析：因為一開始沒仔細看題，沒注意到是嚴格的每5分鐘選一次，導致往DP的方向想了半天，WA一次，又因為沒注意在結束時刻的課是不能選的(題目也沒說太清楚)，又WA了一次...杯具。

??????? 其實這個題就是一個貪心，因為n很小，n^2就可以過，所以實現很簡單：因為每嚴格5分鐘選一次，我們就可以枚舉第一次選課的時間，因為枚舉超過5次之后就和往前數第5次重合了，且不如那一個優(因為少考慮了一個)，所以我們只枚舉從最早的開始點開始的5個點就可以了。如果當前的時間有2個或以上的課可以選，則選結束時間最早的那個。

附代碼：

View Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

int n,ans;
int x[510],y[510];
int Min,Max,tans,pos;
bool b[510];
int main()
{
for (scanf("%d",&n);n;scanf("%d",&n))
    {
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        ans=0;
        Min=200000;Max=0;
for (int i=1;i<=n;i++)
        {
         scanf("%d%d",&x[i],&y[i]);
         Min=min(Min,x[i]);
         Max=max(y[i],Max);
         }
for (int i=0;i<5;i++)
        {
            memset(b,false,sizeof(b));
            tans=0;
for (int j=i;j<=1000;j+=5)
            {
                pos=-1;
for (int k=1;k<=n;k++)
if (!b[k] && x[k]<=j && y[k]>j)
if (pos==-1 || y[pos]>y[k]) pos=k;
if (pos!=-1)
                {
                          tans++;
                          b[pos]=true;
                          } 
                }
            ans=max(ans,tans);
            }
        printf("%d\n",ans);
        }

//system("pause");
    return 0;
    }