【前驅(qū)】：在指定長度的棍子中找到能組成最大周長三角形的三根棍子
鏈接：https://www.nowcoder.com/acm/contest/134/A
來源：牛客網(wǎng)
題目描述
鐵子從森林里收集了n根木棍，她開始將它們按順序的排成一排，從左到右依次為1到n，她回想起
在數(shù)學課上老師教她的三角形知識，她開始從這些木棍中間找三根木棍來組成一個周長最大的三角形，
這時她的兄弟順溜偷偷的溜了過來，偷走了第i根木棍，現(xiàn)在她想知道現(xiàn)在能夠組成周長最大的三角形
的周長是多少？
輸入描述:
第一行兩個整數(shù)n和q。(1 ≤ n, q ≤ 105)
第二行n個整數(shù)表示第i根木棍的長度ai。(1 ≤ ai ≤ 109)
接下來q行，每行一個整數(shù)表示被順溜偷走的木棍編號。注意每行的事件是獨立的，也就是說每一次操作都是對于原來的n根木棍進行的。
輸出描述:
對于每個詢問輸出一行表示答案，如果刪除木棍后無法組成三角形則輸出 -1 。
示例1
輸入
復制
6 2
1 2 3 4 5 6
6
5
輸出
復制
12
13
【代碼】：
#include<string>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<algorithm>
#include<vector>
#include<map>
#include<cctype>
#include<stack>
#include<sstream>
#include<list>
#include<assert.h>
#include<bitset>
#include<numeric>
using namespace std;typedef long long ll;
typedef unsigned long long ULL;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int maxn = 1e5 + 100;
const int maxm = 100;
const double PI = acos(-1.0);
const double eps = 1e-8;
//const int dx[] = {-1,1,0,0,1,1,-1,-1};
//const int dy[] = {0,0,1,-1,1,-1,1,-1};
const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,1,-1};const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dir[6][3]={ {0,0,1},{0,0,-1},{-1,0,0},{1,0,0},{0,1,0},{0,-1,0} };ll n,q,p;
struct node
{ll x,id;
}a[maxn];bool cmp(node a, node b)
{return a.x>b.x; //從最大值開始枚舉
}ll solve()
{for(ll i=1; i+2<=n; i++) //i+2最大值不能超過n{ll k1=i,k2=i+1,k3=i+2; //模擬指針if(a[i].id == p) { k1++; k2++; k3++;} //遇到要刪除的目標，指針后移else if(a[i+1].id == p) { k2++; k3++; }else if(a[i+2].id == p) { k3++; }if(a[k1].x < a[k2].x + a[k3].x) return a[k1].x + a[k2].x + a[k3].x; //合法返回周長}return -1;
}
int main()
{scanf("%lld%lld",&n,&q);for(ll i=1;i<=n;i++){a[i].id=i;scanf("%lld",&a[i].x);}sort(a+1,a+n+1,cmp);while(q--){scanf("%lld",&p);printf("%lld\n",solve());}
}
轉(zhuǎn)載于:https://www.cnblogs.com/Roni-i/p/9193666.html
總結
以上是生活随笔為你收集整理的牛客网 小白赛4 A三角形【贪心】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
