区間最大オーバーラップ数
2412 ワード
http://acm.nyist.net/JudgeOnline/problem.php?pid=220
十分な会場にイベントを準備して、できるだけ少ない会場を利用したいです。有効な欲張りアルゴリズムを設計して手配します。(この問題は実際には有名な図の着色問題です。個々の活動を図の頂点として、不適合活動間をエッジで接続します。隣接する頂点に色の最小着色数を持たせて、探したい最小会場数に対応します。)要求:与えられたk個の予定されているイベントに対して、最低会場のスケジュールをプログラミングして計算します。
このn個の活動を効果的に手配するために、まずn個の活動区間の2 n個の端点を並べ替える。その後,走査アルゴリズムを用いて,左から右にかけて直線全体を走査した。イベントの開始時刻または終了時刻の各イベントポイントに会場を設けます。開始時刻になると、空いた会場にイベントが予定されています。終了時刻になると、イベント用の会場は空き会場スタックに解放され、すでに使用されています。このようにスキャンした後、最大m会場(mは最大重複区間数)を手配しました。
#include
#include
#include
using namespace std;
int main(){
int t;
scanf("%d",&t);
while(t--) {
int n;
scanf("%d",&n);
int sum=0;
int arr[410];
memset(arr,0,sizeof(arr));
for(int i=0;ir)
{
l^=r;
r^=l;
l^=r;
}
for(int j=l;j<=r;j++)
{
arr[j]++;
sum=max(sum,arr[j]);
}
}
printf("%d
",sum*10);
}
return 0;
}
http://www.scut.edu.cn/oj/ タイトル:1924http://blog.csdn.net/cxllyg/article/details/8200395 十分な会場にイベントを準備して、できるだけ少ない会場を利用したいです。有効な欲張りアルゴリズムを設計して手配します。(この問題は実際には有名な図の着色問題です。個々の活動を図の頂点として、不適合活動間をエッジで接続します。隣接する頂点に色の最小着色数を持たせて、探したい最小会場数に対応します。)要求:与えられたk個の予定されているイベントに対して、最低会場のスケジュールをプログラミングして計算します。
このn個の活動を効果的に手配するために、まずn個の活動区間の2 n個の端点を並べ替える。その後,走査アルゴリズムを用いて,左から右にかけて直線全体を走査した。イベントの開始時刻または終了時刻の各イベントポイントに会場を設けます。開始時刻になると、空いた会場にイベントが予定されています。終了時刻になると、イベント用の会場は空き会場スタックに解放され、すでに使用されています。このようにスキャンした後、最大m会場(mは最大重複区間数)を手配しました。
#include
#include
#include
#include
#include
using namespace std;
struct point{
int time,flag;
}arr[20010];
int cmp(const void *a,const void * b)
{
return (*(point*)a).time-(*(point*)b).time;
}
int main(){
int n,a;
scanf("%d",&n);
n<<=1;
for(int i=0;icnt)
cnt=curr;
/* arr[i]==arr[i+1] . cur>cnt arr[i]==arr[i+1] ,i+1 ,
。 i+1 , i , ,
, cnt ; i+1 , i ,
, ,
i+1 , i+1 cnt , i
。*/
}
printf("%d
",cnt);
return 0;
}
/**************************************************************
Problem: 1924
User: 201530542552
Language: C++
Result: Accepted
Time:12 ms
Memory:1120 kb
****************************************************************/