題目背景
曹操平定北方以后,公元 208 年,率領大軍南下,進攻劉表。他的人馬還沒有到荊州,劉表已經病死。他的兒子劉琮聽到曹軍聲勢浩大,嚇破了膽,先派人求降了。
孫權任命周瑜為都督,撥給他三萬水軍,叫他同劉備協力抵抗曹操。
隆冬的十一月,天氣突然回暖,刮起了東南風。
沒想到東吳船隊離開北岸大約二里距離,前面十條大船突然同時起火。火借風勢,風助火威。十條火船,好比十條火龍一樣,闖進曹軍水寨。那里的船艦,都擠在一起,又躲不開,很快地都燒起來。一眨眼工夫,已經燒成一片火海。
曹操氣急敗壞的把你找來,要你鉆入火海把連環線上著火的船只的長度統計出來!
題目描述
給定每個起火部分的起點和終點,請你求出燃燒位置的長度之和。
輸入格式
第一行一個整數,表示起火的信息條數?n。
接下來?n?行,每行兩個整數?a,b,表示一個著火位置的起點和終點(注意:左閉右開)。
輸出格式
輸出一行一個整數表示答案。
輸入輸出樣例
輸入 #1復制
3 -1 1 5 11 2 9
輸出 #1復制
11
說明/提示
數據規模與約定
對于全部的測試點,保證?1≤n≤2×104,?231≤a<b<231,且答案小于?231。
代碼1:差分:80分,由于mn和mx的值超過1e8。
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MX 20005
using namespace std;
int n;?
int a[MX]= {0},d[MX];
int main() {
cin>>n;
int mn = 1e9+7,mx = -1e9+7;;
while(n--)
{
int x,y;
cin>>x>>y;
d[x] += 1;
d[y] += -1;
mn = min(mn,x);
mx = max(mx,y);
}
int cnt = 0;
for(int i = mn;i <= mx;i++)
{
a[i] = a[i-1] + d[i];
if(a[i])
{
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}
代碼二:模擬
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MX 20005
using namespace std;
int n;?
int a[MX],b[MX];
int main() {
cin>>n;
for(int i = 1;i <= n;i++)
{
cin>>a[i]>>b[i];
}
sort(a+1,a+n+1);
sort(b+1,b+n+1);
int cnt = 0;
for(int i = 1;i <= n;i++)
{
cnt = cnt + b[i] - a[i];
if(i < n)
{
if(b[i] > a[i+1])
{
cnt = cnt - (b[i] - a[i+1]);
}
}?
}
cout<<cnt<<endl;
return 0;
}