https://ac.nowcoder.com/acm/contest/318#question
C++版本一
题解：
排序+DFS
竟然没有TLE
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
typedef __int128 lll;
const int N=10000;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
struct node{
int id;
ll x;
}a[N];
bool cmp(node a,node b){
return a.x<b.x;
}
ll b[5];
int vis[N];
ll ans=0;
void dfs(int c){
if(c==3){
if(b[1]+b[2]>b[3]&&b[1]+b[3]>b[2]&&b[3]+b[2]>b[1]){
ans=b[1]+b[2]+b[3];
}
return;
}
for(int i=n;i>0;i--){
if(ans!=-1){
break;
}
if(!vis[a[i].id]){
vis[a[i].id]=1;
b[c+1]=a[i].x;
dfs(c+1);
vis[a[i].id]=0;
}
}
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
scanf("%d",&t);
int T=0;
while(t--){
scanf("%d%d",&n,&q);
printf("Case #%d:\n",++T);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i].x);
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
while(q--){
scanf("%d",&k);
vis[k]=1;
ans=-1;
dfs(0);
vis[k]=0;
printf("%lld\n",ans);
}
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
题解：这是一道贪心题，首先对n根木棍降序排序，然后对于每次询问，枚举最长的木棍i，那么次长和最短的木棍的编号也确定了是i+1，i+2，如果这三根里有一根是被拿走了的话，那么就往后顺延一根即可，然后判断一下最长的那根的长度是不是小于其余两根之和，是的话这n-1根木棍能构成的三角形的最大周长就确定了，否则的话，说明不不存在一个三角形以第i根木棍为最长的边（因为此时取的较短的那两根木棍的长度之和必定是从第i+1根到第n根木棍里能取到的最长的了，当然被拿走了的那根木棍是无法取的，因为我们之前对木棍按降序排序了），那么继续枚举下一根木棍即i+1根木棍为最长的木棍。接下来证明为什么枚举到的第一组能组成三角形的三根木棍的长度之和是所有能组成三角形的木棍组合里长度最长的，假设有2个满足条件的组合，一个木棍组合是i ，i+1，i+2，另一个是i+1,i+2,i+3, 因为我们之前对木棍按降序排序，所以第一个组合的长度和是大于等于第二个组合的长度和的。注意一点就是，1e9 + 1e9 + 1e9是超过int范围的，所以得用long long。
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
struct node
{
int id;
long long len;
}a[maxn];
bool cmp(const struct node&a,const struct node&b)
{
return a.len>b.len;
}
int main()
{
int t,n,q,x,icase=0;
long long maxx;
scanf("%d",&t);
while(t--)
{
memset(a,0,sizeof(a));
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i].len);
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
printf("Case #%d:\n",++icase);
while(q--)
{
maxx=-1;
scanf("%d",&x);
for(int i=1;i<=(n-2);i++)
{
int f,g,h;
if(a[i].id==x)
{
continue;
}
else
if(a[i+1].id==x)
{
f=i;
g=i+2;
h=i+3;
}
else
if(a[i+2].id==x)
{
f=i;
g=i+1;
h=i+3;
}
else
{
f=i;
g=i+1;
h=i+2;
}
if(a[f].len<(a[g].len+a[h].len))
{
maxx=a[f].len+a[g].len+a[h].len;
break;
}
}
printf("%lld\n",maxx);
}
}
return 0;
} C++版本三
题解：：先对边长数组排序，然后每次查询3个for枚举3条边的长度也可以过。可以知道无法构成三角形的边长数组a的长度最大是44，是斐波那契数列，因为3条边无法构成三角形是第三条边长度>=较小的2边之和，为了使a数组元素最长，使相邻三条边的长度满足a[i+2]=a[i+1]+a[i],可以发现这个是斐波那契数列，然后第45项>1e10,所以a数组的最大长度是44. 然后由这个结论可以知道每次查询的时候3个for枚举最坏也就是枚举44^3+1次就可以知道答案，复杂度是10*100*44^3.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 2005
struct node
{
int id;
ll len;
}a[maxn];
bool cmp(const struct node&a,const struct node&b)
{
return a.len>b.len;
}
int main()
{
int t,n,q,icas=0;
ll ans;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i].len);
a[i].id=i;
}
printf("Case #%d:\n",++icas);
sort(a+1,a+n+1,cmp);
while(q--)
{
int x;
ans=-1;
scanf("%d",&x);
for(int i=1;i<=n;i++)
{
if(a[i].id==x) continue;
for(int j=i+1;j<=n;j++)
{
if(a[j].id==x) continue;
for(int v=j+1;v<=n;v++)
{
if(a[v].id==x) continue;
if(a[i].len<a[j].len+a[v].len)
{
ans=a[j].len+a[v].len+a[i].len;
break;
}
}
if(ans!=-1)
break;
}
if(ans!=-1)
break;
}
printf("%lld\n",ans);
}
}
return 0;
}
京公网安备 11010502036488号