【贪心】【RQNOJ】橘子结配

题目描述

深秋来临，这是辛勤了一年享受丰收的季节，freeze大牛在闲暇时间来到郊外的橘园，想在美丽的秋景中体味丰收的欣喜与温暖。
这个橘园一共种有若干个橘子，现在他们想利用一天的时间，将其中一棵橘子树上的所有橘子都摘下来装入到一个大篮子中，他们根据过去的经验认为，一个篮子即使再大，它也有自己能装橘子的一个最大承受质量，他们在想只要能使能装入的橘子总质量最大（也就是不超过篮子的最大承受质量的最大装橘总质量）就算完成了任务。
但是这个橘园内种的橘子又有一个独特的性质：橘子可以互相结配（可以任意地结配，但是在第一次结配时，也就是结配的2个都是未结配的橘子，至少要有1个橘子已经从树上摘了下来，后面由于这棵橘子树就已经掌握了摘取本领，也就不再需要摘取橘子，就可以直接进行结配了），而且在结配或摘取的时候本身会产生一个损耗值（本题所述的损耗值均为其包含的所有橘子子损耗值的总合，橘子包含未结配与结配2种形态）。
所以此时即使想使能装入的橘子总质量最大，也会因为橘子质量本身发生损耗而减小，现在他们必须先算出这些橘子的最小损耗总值才能开始摘取，以保证其质量。
[数据规模]
n<=50
r最大不超过1000
From 宜昌6中(初中)

输入格式

输入有2行，
第1行1个数，即这棵橘子树上共有n个橘子；
第2行n个数，即这棵橘子树上每个橘子的损耗值r。

输出格式

输出有2行，
第一行首先算出这些橘子的最小损耗总值；
第二行判断它是否是素数，如果是，则输出Yes，否则输出No。

样例输入

6 121 80 121 368 103 421

样例输出

2933 No

三维状态图像

---

 

题目有些描述不清，其实就是合并果子改编，然后最小的需要加两次。
判断素数很简单。

#include<stdio.h> #include<stdlib.h> #include<iostream> #include<math.h> using namespace std; int n,a[100]; long long ans; int cmp(const void*a,const void*b) { int c=*(int*)a,d=*(int*)b; if (c<d) return -1; if (c>d) return 1; return 0; } bool zhi(long long x) { if (x<2) return false; if (x==2) return true; for (int i=2;i<=sqrt(x);++i) if (x%i==0) return false; return true; } int main() { scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&a[i]); qsort(a,n+1,sizeof(int),cmp); ans=a[1]; while (n>1) { qsort(a,n+1,sizeof(int),cmp); swap(a[n],a[1]); qsort(a,n,sizeof(int),cmp); swap(a[n-1],a[1]); ans+=a[n]+a[n-1]; a[n-1]+=a[n]; --n; } printf("%lld/n",ans); if (zhi(ans)) printf("Yes/n"); else printf("No/n"); return 0; }