程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> uvalive 4328(貪心)

uvalive 4328(貪心)

編輯:關於C++

題意:有n對夫妻要舉行婚禮,然後一個牧師需要在所有婚禮上舉行一個儀式,每個儀式必須占用婚禮一半以上的時間且不能被打斷,給出了n個婚禮的開始和結束時間,問是否可以讓牧師在所有婚禮都舉行儀式。

題解:先按婚禮起始時間排序,然後遍歷所有婚禮看是否有足夠時間舉行儀式。

 

#include 
#include 
using namespace std;
const int N = 100005;
struct Couple {
	int s, t, d;
}cou[N];
int n;

bool cmp(Couple a, Couple b) {
	return a.s + a.d < b.s + b.d;
}

bool judge() {
	int ss = cou[0].s;
	for (int i = 0; i < n - 1; i++) {
		int temp = ss + cou[i].d;
		if (temp >= cou[i + 1].s && temp + cou[i + 1].d <= cou[i + 1].t)
			ss = temp;
		else if (temp < cou[i + 1].s)
			ss = cou[i + 1].s;
		else
			return false;
	}
	return true;
}

int main() {
	while (scanf("%d", &n) && n) {
		for (int i = 0; i < n; i++) {
			scanf("%d%d", &cou[i].s, &cou[i].t);
			cou[i].d = (cou[i].t - cou[i].s) / 2 + 1;
		}
		sort(cou, cou + n, cmp);
		if (judge())
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved