samlin961112@gmail.com
(林哲甫)
學校
:
新北市私立南山高級中學
編號 : 220506
來源 : [219.70.213.92]
最後登入時間 ：
2024-04-28 22:43:43
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
vector<pair<int,int>> a(m);
for(int i=0;i<m;i++){
cin>>a[i].first>>a[i].second;
}
sort(a.begin(),a.end());
for(int i=0;i<a.size()-1;i++){
if(a[i]>a[i+1]){
swap(a[i],a[i+1]);
}
if(a[i+1].second<=a[i].second){
a[i]=make_pair(a[i].first,a[i+1].first-1);
a[i+1]=make_pair(a[i+1].second+1,a[i].second);
}else if(a[i+1].first<=a[i].second){
a[i]=make_pair(a[i].first,a[i+1].first-1);
a[i+1]=make_pair(a[i].second+1,a[i+1].second);
}
}
int sum=0;
for(int i=0;i<a.size();i++){
if(a[i].second>a[i].first){
sum+=a[i].second-a[i].first;}
}
cout<<n-sum;
}
zhoudaniel02@gmail.com
(周孝倫)
學校
:
銘傳大學
編號 : 235507
來源 : [223.140.157.105]
最後登入時間 ：
2024-04-29 21:31:07
#include
#define int unsigned long long
using namespace std;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
vector> a(m);
for(int i=0;i
cin>>a[i].first>>a[i].second;
}
sort(a.begin(),a.end());
for(int i=0;i
if(a[i]>a[i+1]){
swap(a[i],a[i+1]);
}
if(a[i+1].second<=a[i].second){
a[i]=make_pair(a[i].first,a[i+1].first-1);
a[i+1]=make_pair(a[i+1].second+1,a[i].second);
}else if(a[i+1].first<=a[i].second){
a[i]=make_pair(a[i].first,a[i+1].first-1);
a[i+1]=make_pair(a[i].second+1,a[i+1].second);
}
}
int sum=0;
for(int i=0;i
if(a[i].second>a[i].first){
sum+=a[i].second-a[i].first;}
}
cout<}
我想到一個概念，就是只儲存每一個區間的開頭-1的值和結尾的值，生序排序並去掉成對的數字後會得到一個數列b，這個數列的意義是從b0到0都是蹲的或站的，b2到b1也是，這樣就不會TLE了，不過這個邏輯用java寫，倒數兩個測資會MLE，因為我後面把代碼閹割到只剩輸入和只輸出數字1還是會MLE
這樣做的時間複雜度就會是O(nlog(n))了，n是區間的數量，空間複雜度則是O(n)
下面是第一筆測資
10
5
2 6
3 6
4 6
6 9
7 8
| 區間\人 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | t | t | ||||||||
| 2 | t | t | f | |||||||
| 3 | t | t | t | t | ||||||
| 4 | t | t | t | t | t | t | ||||
| 5 | t | t | t | t | f | t | t | |||
| 最終端點 | t | t | t | t | t | t |
空白是默認值為false
下面是我的代碼
Scanner sc=new Scanner(System.in);Java特有的麻煩的輸入流程
List<Integer>point=new ArrayList<>();用來儲存區間的端點的值
輸入的部分
int p=sc.nextInt();
int w=sc.nextInt();
sc.nextLine();
for(int i=1;i<=w;i++) {
String[]s=sc.nextLine().split(" ");
point.add(Integer.parseInt(s[0])-1); 開頭的端點要-1才能存入
point.add(Integer.parseInt(s[1]));
}
將輸入的所有端點生序排序，並去除成對重複的數字
Collections.sort(point);
for(int i=1;i<point.size();i++)
if(point.get(i)==point.get(i-1)) {
point.remove(i);
point.remove(i-1);
i--;
}
計算端點和站著的人數之間的關係:
先加上最小的端點的值和末尾到倒數第一個端點的距離
int time=point.get(0)+p-point.get(point.size()-1);
再依次加上端點dn與端點dn-1間的距離(n從2開始，每次迭代+2)
for(int i=2;i<point.size()-1;i+=2)
time+=point.get(i)-point.get(i-1);
System.out.println(time);