PDD11. 种树
描述
小多想在美化一下自己的庄园。他的庄园毗邻一条小河，他希望在河边种一排树，共 M 棵。小多采购了 N 个品种的树，每个品种的数量是 Ai (树的总数量恰好为 M)。但是他希望任意两棵相邻的树不是同一品种的。小多请你帮忙设计一种满足要求的种树方案。
输入描述
第一行包含一个正整数 N，表示树的品种数量。输出描述
输出一行，包含 M 个正整数，分别表示第 i 棵树的品种编号 (品种编号从1到 N)。若存在多种可行方案，则输出字典序最小的方案。若不存在满足条件的方案，则输出"-"。示例1
输入:
3 4 2 1
输出:
1 2 1 2 1 3 1
C++ 解法, 执行用时: 2ms, 内存消耗: 404KB, 提交时间: 2020-10-31
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
int main()
{
int num = 0, temp = 0;
cin >> num;
vector<int> treeNum;
for(int i = 0; i < num; i++)
{
cin >> temp;
treeNum.push_back(temp);
}
vector<int> frontTree, backTree;
for(int i = 0; i < num; i++)
{
if(frontTree.size() <= backTree.size())
frontTree.insert(frontTree.end(), treeNum[i], i+1);
else
backTree.insert(backTree.end(), treeNum[i], i+1);
}
int gapInt = frontTree.size() - backTree.size();
vector<int> finalTree;
int bothMax = ((gapInt >= 0) ? frontTree.size() : backTree.size());
for(int i = 0; i < bothMax; i++)
{
if(i < frontTree.size())
finalTree.push_back(frontTree[i]);
if(i < backTree.size())
finalTree.push_back(backTree[i]);
}
int finalNum = finalTree.size();
int adjNum = ((gapInt == 1) || (gapInt == 0)) ? 0: (gapInt > 1 ? (gapInt - 1) : (-1)*gapInt);
int adjVal = finalTree.back();
if(adjNum > 0)
{
//finalTree.resize(finalTree.size() + 2*adjNum);
auto iteratorEnd = find(finalTree.begin(), finalTree.end(), adjVal);
if((iteratorEnd - finalTree.begin() + 1) >= adjNum)
{
auto iteratorAdjBegin = iteratorEnd - adjNum;
auto iteratorAdjEnd = finalTree.begin() + finalNum;
vector<int> againAdj(iteratorAdjBegin, iteratorAdjEnd);
sort(againAdj.begin(), againAdj.end());
auto iterValBegin = find(againAdj.begin(), againAdj.end(), adjVal);
auto iterValEndR = find(againAdj.rbegin(), againAdj.rend(), adjVal);
auto iterValEnd = iterValEndR.base();
vector<int> firstVec(iterValBegin, iterValEnd);
//againAdj.erase(adjVal);
vector<int> secondVec;
for_each(againAdj.begin(), againAdj.end(),
[adjVal, &secondVec](int &ii) {if (ii != adjVal) { secondVec.push_back(ii); }});
int ij = 0;
for (ij = 0; ij < secondVec.size(); ij++)
{
againAdj[ij * 2] = firstVec[ij];
againAdj[ij * 2 + 1] = secondVec[ij];
}
againAdj[ij * 2] = firstVec[ij];
finalTree.insert(iteratorAdjBegin, againAdj.begin(), againAdj.end());
}
else{
cout << "-" << endl;
return 0;
}
}
/*if(adjNum > 0)
{
finalTree.resize(finalTree.size() + 2*adjNum);
auto iteratorEnd = find(finalTree.begin(), finalTree.end(), adjVal);
if((iteratorEnd - finalTree.begin() + 1) >= adjNum)
{
for(int i = 0; i < adjNum; i++){
//iteratorEnd = find(finalTree.begin(), finalTree.end(), adjVal);
--iteratorEnd;
iteratorEnd = finalTree.insert(iteratorEnd, adjVal);
}
}
else{
cout << "-" << endl;
return 0;
}
}
auto iteratorAdjBegin = find(finalTree.begin(), finalTree.end(), adjVal);
auto iteratorAdjEnd = finalTree.begin() + finalNum;
vector<int> againAdj(iteratorAdjBegin, iteratorAdjEnd);
sort(againAdj.begin(), againAdj.end());
auto iterValBegin = find(againAdj.begin(), againAdj.end(), adjVal);
auto iterValEndR = find(againAdj.rbegin(), againAdj.rend(), adjVal);
auto iterValEnd = iterValEndR.base();
vector<int> firstVec(iterValBegin, iterValEnd);
//againAdj.erase(adjVal);
vector<int> secondVec;
for_each(againAdj.begin(), againAdj.end(),
[adjVal, &secondVec](int &ii) {if (ii != adjVal) { secondVec.push_back(ii); }});
int ij = 0;
for (ij = 0; ij < secondVec.size(); ij++)
{
againAdj[ij * 2] = firstVec[ij];
againAdj[ij * 2 + 1] = secondVec[ij];
}
againAdj[ij * 2] = firstVec[ij];
finalTree.insert(iteratorAdjBegin, againAdj.begin(), againAdj.end()); */
for(int i = 0; i < finalNum; i++)
cout << finalTree[i] << " ";
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 428KB, 提交时间: 2020-07-28
#include<stdio.h>
#include<malloc.h>
int main()
{
int n, num = 0;
int *a;
scanf("%d", &n);
a = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
num += a[i];
}
for (int i = 0; i < n; i++)
if (a[i] > (num + 1) / 2) {
printf("--");
return 1;
}
int i, lastv = 1000;
while (1) {
for (i = 0; i < n; i++) {
if (a[i] == num / 2 + 1) {
lastv = i;
printf("%d ", i + 1);
a[i]--;
num--;
break;
}
}
for (i = 0; i < n; i++) {
if (a[i] != 0 && i != lastv) {
lastv = i;
printf("%d ", i + 1);
a[i]--;
num--;
break;
}
}
if (num==0)
break;
}
return 0;
}
C++ 解法, 执行用时: 2ms, 内存消耗: 504KB, 提交时间: 2020-10-31
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
int main()
{
int num = 0, temp = 0;
cin >> num;
vector<int> treeNum;
for(int i = 0; i < num; i++)
{
cin >> temp;
treeNum.push_back(temp);
}
vector<int> frontTree, backTree;
for(int i = 0; i < num; i++)
{
if(frontTree.size() <= backTree.size())
frontTree.insert(frontTree.end(), treeNum[i], i+1);
else
backTree.insert(backTree.end(), treeNum[i], i+1);
}
int gapInt = frontTree.size() - backTree.size();
vector<int> finalTree;
int bothMax = ((gapInt >= 0) ? frontTree.size() : backTree.size());
for(int i = 0; i < bothMax; i++)
{
if(i < frontTree.size())
finalTree.push_back(frontTree[i]);
if(i < backTree.size())
finalTree.push_back(backTree[i]);
}
int finalNum = finalTree.size();
int adjNum = ((gapInt == 1) || (gapInt == 0)) ? 0: (gapInt > 1 ? (gapInt - 1) : (-1)*gapInt);
int adjVal = finalTree.back();
if(adjNum > 0)
{
//finalTree.resize(finalTree.size() + 2*adjNum);
auto iteratorEnd = find(finalTree.begin(), finalTree.end(), adjVal);
if((iteratorEnd - finalTree.begin() + 1) >= adjNum)
{
auto iteratorAdjBegin = iteratorEnd - adjNum;
auto iteratorAdjEnd = finalTree.begin() + finalNum;
vector<int> againAdj(iteratorAdjBegin, iteratorAdjEnd);
sort(againAdj.begin(), againAdj.end());
auto iterValBegin = find(againAdj.begin(), againAdj.end(), adjVal);
auto iterValEndR = find(againAdj.rbegin(), againAdj.rend(), adjVal);
auto iterValEnd = iterValEndR.base();
vector<int> firstVec(iterValBegin, iterValEnd);
//againAdj.erase(adjVal);
vector<int> secondVec;
for_each(againAdj.begin(), againAdj.end(),
[adjVal, &secondVec](int &ii) {if (ii != adjVal) { secondVec.push_back(ii); }});
int ij = 0;
for (ij = 0; ij < secondVec.size(); ij++)
{
againAdj[ij * 2] = firstVec[ij];
againAdj[ij * 2 + 1] = secondVec[ij];
}
againAdj[ij * 2] = firstVec[ij];
finalTree.insert(iteratorAdjBegin, againAdj.begin(), againAdj.end());
}
else{
cout << "-" << endl;
return 0;
}
}
/*if(adjNum > 0)
{
finalTree.resize(finalTree.size() + 2*adjNum);
auto iteratorEnd = find(finalTree.begin(), finalTree.end(), adjVal);
if((iteratorEnd - finalTree.begin() + 1) >= adjNum)
{
for(int i = 0; i < adjNum; i++){
//iteratorEnd = find(finalTree.begin(), finalTree.end(), adjVal);
--iteratorEnd;
iteratorEnd = finalTree.insert(iteratorEnd, adjVal);
}
}
else{
cout << "-" << endl;
return 0;
}
}
auto iteratorAdjBegin = find(finalTree.begin(), finalTree.end(), adjVal);
auto iteratorAdjEnd = finalTree.begin() + finalNum;
vector<int> againAdj(iteratorAdjBegin, iteratorAdjEnd);
sort(againAdj.begin(), againAdj.end());
auto iterValBegin = find(againAdj.begin(), againAdj.end(), adjVal);
auto iterValEndR = find(againAdj.rbegin(), againAdj.rend(), adjVal);
auto iterValEnd = iterValEndR.base();
vector<int> firstVec(iterValBegin, iterValEnd);
//againAdj.erase(adjVal);
vector<int> secondVec;
for_each(againAdj.begin(), againAdj.end(),
[adjVal, &secondVec](int &ii) {if (ii != adjVal) { secondVec.push_back(ii); }});
int ij = 0;
for (ij = 0; ij < secondVec.size(); ij++)
{
againAdj[ij * 2] = firstVec[ij];
againAdj[ij * 2 + 1] = secondVec[ij];
}
againAdj[ij * 2] = firstVec[ij];
finalTree.insert(iteratorAdjBegin, againAdj.begin(), againAdj.end()); */
for(int i = 0; i < finalNum; i++)
cout << finalTree[i] << " ";
return 0;
}
C 解法, 执行用时: 3ms, 内存消耗: 376KB, 提交时间: 2020-08-02
#include<stdio.h>
#include<malloc.h>
int main()
{
int n, num = 0;
int *a;
scanf("%d", &n);
a = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
num += a[i];
}
for (int i = 0; i < n; i++)
if (a[i] > (num + 1) / 2) {
printf("--");
return 1;
}
int i, lastv = 1000;
while (1) {
for (i = 0; i < n; i++) {
if (a[i] == num / 2 + 1) {
lastv = i;
printf("%d ", i + 1);
a[i]--;
num--;
break;
}
}
for (i = 0; i < n; i++) {
if (a[i] != 0 && i != lastv) {
lastv = i;
printf("%d ", i + 1);
a[i]--;
num--;
break;
}
}
if (num==0)
break;
}
return 0;
}
C 解法, 执行用时: 3ms, 内存消耗: 376KB, 提交时间: 2020-05-18
#include<stdio.h>
#include<malloc.h>
int main()
{
int n, num = 0;
int *a;
scanf("%d", &n);
a = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
num += a[i];
}
for (int i = 0; i < n; i++)
if (a[i] > (num + 1) / 2) {
printf("--");
return 1;
}
int i, lastv = 1000;
while (1) {
for (i = 0; i < n; i++) {
if (a[i] == num / 2 + 1) {
lastv = i;
printf("%d ", i + 1);
a[i]--;
num--;
break;
}
}
for (i = 0; i < n; i++) {
if (a[i] != 0 && i != lastv) {
lastv = i;
printf("%d ", i + 1);
a[i]--;
num--;
break;
}
}
if (num==0)
break;
}
return 0;
}