C.LongestSimpleCycle(貪心)-創(chuàng)新互聯(lián)

Problem - 1476C - Codeforces

在資陽等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都做網(wǎng)站、網(wǎng)站建設(shè)、外貿(mào)營銷網(wǎng)站建設(shè) 網(wǎng)站設(shè)計(jì)制作按需求定制制作,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站制作,全網(wǎng)營銷推廣,外貿(mào)網(wǎng)站制作,資陽網(wǎng)站建設(shè)費(fèi)用合理。

你有n條鏈，第i條鏈由ci個(gè)頂點(diǎn)組成。每條鏈中的頂點(diǎn)沿鏈從1到ci獨(dú)立編號。換句話說，第i條鏈?zhǔn)怯蒫i個(gè)頂點(diǎn)和連接第j個(gè)和(j+1)個(gè)頂點(diǎn)的(ci-1)條邊組成的無向圖，每1≤j

現(xiàn)在你決定以下列方式將各鏈合并為一個(gè)圖。

第一條鏈被跳過。
第i條鏈的第1個(gè)頂點(diǎn)通過一條邊與第(i-1)條鏈的第i個(gè)頂點(diǎn)相連。
第i條鏈的最后一個(gè)(ci-th)頂點(diǎn)與第(i-1)條鏈的bi-th頂點(diǎn)以邊連接。
第一個(gè)測試案例的圖片。虛線是聯(lián)合過程中添加的邊。
計(jì)算結(jié)果圖中最長的簡單循環(huán)的長度。

一個(gè)簡單的循環(huán)是一個(gè)鏈，其中第一個(gè)和最后一個(gè)頂點(diǎn)也是相連的。如果你沿著簡單循環(huán)走，這個(gè)循環(huán)的每個(gè)頂點(diǎn)都會(huì)被精確訪問一次。

輸入
第一行包含一個(gè)整數(shù)t（1≤t≤1000）--測試案例的數(shù)量。

每個(gè)測試案例的第一行包含一個(gè)整數(shù)n（2≤n≤105）--你的鏈的數(shù)量。

每個(gè)測試用例的第二行包含n個(gè)整數(shù)c1,c2,...,cn (2≤ci≤109) - 相應(yīng)鏈中頂點(diǎn)的數(shù)量。

每個(gè)測試用例的第三行包含n個(gè)整數(shù)a1,a2,...,an（a1=-1；1≤ai≤ci-1）。

每個(gè)測試案例的第四行包含n個(gè)整數(shù)b1,b2,...,bn（b1=-1；1≤bi≤ci-1）。

a1和b1都等于-1，它們在圖的構(gòu)建中并沒有使用，只是為了索引的一致性而給出。我們保證所有測試案例的n之和不超過105。

輸出
對于每個(gè)測試案例，打印最長的簡單循環(huán)的長度。

例子
inputCopy
3
4
3 4 3 3
-1 1 2 2
-1 2 2 3
2
5 6
-1 5
-1 1
3
3 5 2
-1 1 1
-1 3 5
輸出拷貝
7
11
8
注意
在第一個(gè)測試案例中，最長的簡單循環(huán)顯示在下面。

我們不能用第一條鏈來增加它，因?yàn)樵谶@種情況下，它不會(huì)是簡單的--第二條鏈上的頂點(diǎn)2會(huì)破壞簡單性。

題解:

設(shè)sum為此時(shí)的長度

x為(a[i],b[i])最靠近1,y為最靠近c(diǎn)[i]的

我們從右往左枚舉右邊界,如果sum + x + c[i] - y< c[i]

說明此時(shí)重新枚舉的c[i]為右邊界更優(yōu),或者此時(shí)x == y說明左邊界已經(jīng)走到頭需重新枚舉右邊界

sum = c[i]

或者如果sum + x + c[i] - y >= c[i]

sum肯定要加上這一部分

#include#include
#include#include#include#include#include#include#includeusing namespace std;
#define int long long
int a[100050];
int b[100050];
int c[100050]; 
void solve()
{
	int n;
	cin >>n;
	for(int i = 1;i<= n;i++)
	cin >>c[i];
	for(int i = 1;i<= n;i++)
	cin >>a[i];
	for(int i = 1;i<= n;i++)
	{
		cin >>b[i];
	}
	int x = 1,y = c[n];
	int sum = 0,ans = 0;
	for(int i = n;i >1;i--)
	{
		if(x == y||sum + x + c[i]-y< c[i])
		{
			sum = c[i];
		}
		else
		{
			sum += x + c[i] - y + 1;//+1是因?yàn)閮蓷l鏈之間要連邊
		}
		y = max(a[i],b[i]);
		x = min(a[i],b[i]);
		ans = max(ans,sum + y -x +1);//+1是因?yàn)閮蓷l鏈之間要連邊
	}
	cout<< ans<<"\n";
	
}
//0 2 2
signed main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
	int t = 1;
	cin >>t;
    while(t--)
	{

		solve();
	} 
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁題目：C.LongestSimpleCycle(貪心)-創(chuàng)新互聯(lián)
分享網(wǎng)址：http://www.muchs.cn/article48/dhciep.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、做網(wǎng)站、網(wǎng)站建設(shè)、App開發(fā)、面包屑導(dǎo)航、品牌網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

微信小程序開發(fā)