From 9337a04696d520a54958c7a6e537b201ee264573 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Fri, 28 Sep 2018 21:18:07 -0500
Subject: Maximize num of places of prize done!

More practice with C++ vector.---
 PlaygroundCpp/Sources/Playground.cpp | 106 +++++++----------------------------
 1 file changed, 21 insertions(+), 85 deletions(-)

(limited to 'PlaygroundCpp/Sources')

diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index 26e02f2..6892515 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,102 +1,38 @@
-#include <algorithm>
 #include <iostream>
-#include <climits>
 #include <vector>
 //#include <gtest/gtest.h>
 
 using std::vector;
 
-struct Segment {
-	int start, end;
-	bool operator==(const Segment &s1) {
-		return (start == s1.start && end == s1.end);
+vector<int> optimal_summands(int n) {
+	vector<int> summands;
+	if (n < 3) {
+		summands.push_back(n);
+		return summands;
 	}
-};
-
-vector<int> optimal_points(vector<Segment> &segments) {
-	int index = 0;
-	vector<int> points;
-	while (index < segments.size()) {
-		points.push_back(segments[index].end);
-		index = index + 1;
-		while (index < segments.size()
-				&& segments[index].start <= points[points.size() - 1]) {
-			if (segments[index].end < points[points.size() - 1]) {
-				points.back() = segments[index].end;
-			}
-			index = index + 1;
+	int runningSum = 0;
+	for (int i = 1; i < n + 1; i++) {
+		runningSum = runningSum + i;
+		summands.push_back(i);
+		if (runningSum == n) {
+			break;
+		}
+		if (runningSum > n) {
+			summands.pop_back();
+			summands.back() = summands.back() + n - runningSum + i;
+			break;
 		}
 	}
-	return points;
-}
-
-bool sortSeg(Segment i, Segment j) {
-	if (i.start == j.start) {
-		return i.end < j.end;
-	}
-	return i.start < j.start;
+	return summands;
 }
 
-//TEST(SortSegment, Sort1) {
-//	Segment OneFive, TwoFour;
-//	OneFive.start = 1;
-//	OneFive.end = 5;
-//	TwoFour.start = 2;
-//	TwoFour.end = 4;
-//	vector<Segment> a = { TwoFour, OneFive };
-//	std::sort(a.begin(), a.end(), sortSeg);
-//	ASSERT_EQ(a.at(0).start, 1);
-//}
-//
-//TEST(SortSegment, Sort2) {
-//	Segment OneFive, OneFour;
-//	OneFive.start = 1;
-//	OneFive.end = 5;
-//	OneFour.start = 1;
-//	OneFour.end = 4;
-//	vector<Segment> a = { OneFive, OneFour };
-//	std::sort(a.begin(), a.end(), sortSeg);
-//	ASSERT_EQ(a.at(0).end, 4);
-//}
-//
-//TEST(SortSegment, SortWithDups1) {
-//	Segment OneFive, OneFour;
-//	OneFive.start = 1;
-//	OneFive.end = 5;
-//	OneFour.start = 1;
-//	OneFour.end = 4;
-//	vector<Segment> a = { OneFive, OneFour, OneFive};
-//	std::sort(a.begin(), a.end(), sortSeg);
-//	ASSERT_EQ(a.at(0).end, 4);
-//	ASSERT_EQ(a.size(), 3);
-//}
-//
-//TEST(SortSegment, SortAndRemoveDups1) {
-//	Segment OneFive, OneFour;
-//	OneFive.start = 1;
-//	OneFive.end = 5;
-//	OneFour.start = 1;
-//	OneFour.end = 4;
-//	vector<Segment> a = { OneFive, OneFour, OneFive};
-//	std::sort(a.begin(), a.end(), sortSeg);
-//	auto last = std::unique(a.begin(), a.end());
-//	a.erase(last, a.end());
-//	ASSERT_EQ(a.size(), 2);
-//}
 
 int main() {
 	int n;
 	std::cin >> n;
-	vector<Segment> segments(n);
-	for (size_t i = 0; i < segments.size(); ++i) {
-		std::cin >> segments[i].start >> segments[i].end;
-	}
-	std::sort(segments.begin(), segments.end(), sortSeg);
-	auto last = std::unique(segments.begin(), segments.end());
-	segments.erase(last, segments.end());
-	vector<int> points = optimal_points(segments);
-	std::cout << points.size() << "\n";
-	for (size_t i = 0; i < points.size(); ++i) {
-		std::cout << points[i] << " ";
+	vector<int> summands = optimal_summands(n);
+	std::cout << summands.size() << '\n';
+	for (size_t i = 0; i < summands.size(); ++i) {
+		std::cout << summands[i] << ' ';
 	}
 }
-- 
cgit v1.2.3