HDU 2037今年の夏休みはAC
質問リンク:HDU 2037今年の夏休みはACではありません.
典型的な欲張りアルゴリズム問題は,それぞれC言語とC++言語でプログラムを記述する.
いくつかのテレビ番組は、もちろん時間順に見なければならない.もっと多くの番組を見るためには、できるだけ早く一つの番組を見てから別の番組を見て、もっと短い番組を見てからもっと多くの番組を見る必要があります.
C言語プログラムとC++言語プログラムの違いは,ソートのみで呼び出される関数とパラメータが異なる.
他に言うことは、プログラム注釈にあります.
C言語のACプログラムは以下の通りである.
C++言語の
MACプログラムは以下の通りである.
典型的な欲張りアルゴリズム問題は,それぞれC言語とC++言語でプログラムを記述する.
いくつかのテレビ番組は、もちろん時間順に見なければならない.もっと多くの番組を見るためには、できるだけ早く一つの番組を見てから別の番組を見て、もっと短い番組を見てからもっと多くの番組を見る必要があります.
C言語プログラムとC++言語プログラムの違いは,ソートのみで呼び出される関数とパラメータが異なる.
他に言うことは、プログラム注釈にあります.
C言語のACプログラムは以下の通りである.
/* HDU2037 AC */
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100
struct node {
int start;
int end;
} record[MAXN];
int cmp(const void * a, const void * b)
{
struct node *x = (struct node *) a;
struct node *y = (struct node *) b;
return x->end - y->end;
}
int main(void)
{
int n, count, lastend, i;
while(scanf("%d", &n) != EOF) {
//
if(n == 0)
break;
//
for(i=0; i<n; i++)
scanf("%d%d", &record[i].start, &record[i].end);
// :
qsort(record, n, sizeof(record[0]), cmp);
// :
count = 0;
lastend = -1;
for(i=0; i<n; i++) {
if(record[i].start >= lastend) {
count++;
lastend = record[i].end;
}
}
//
printf("%d
", count);
}
return 0;
}
C++言語の
MACプログラムは以下の通りである.
/* HDU2037 AC */
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 100
struct node {
int start;
int end;
} record[MAXN];
bool cmp(const node& a, const node& b)
{
return a.end < b.end;
}
int main()
{
int n, count, lastend, i;
for(;;) {
// n
cin >> n;
//
if(n == 0)
break;
//
for(i=0; i<n; i++)
cin >> record[i].start >> record[i].end;
// :
sort(record, record + n, cmp);
// :
count = 0;
lastend = -1;
for(i=0; i<n; i++) {
if(record[i].start >= lastend) {
count++;
lastend = record[i].end;
}
}
//
cout << count << endl;
}
return 0;
}