P7714 「EZEC-10」排列排序
题目链接
双指针求小区间的长度之和[L,R]满足R大于等于区间内最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int a[1000005];
void solve(){
int n=read();
for(int i=1;i<=n;i++)a[i]=read();
int ma=0;
int ans=0;
for(int l=1,r=1;r<=n;r++){
ma=max(ma,a[r]);
while(l<r&&a[l]==l){
l++;
}
if(r==ma&&l<r){
ans+=r-l+1;
l=r+1;
ma=0;
}
}
cout<<ans<<endl;
}
|
P3611 [USACO17JAN] Cow Dance Show S
题目链接
N个牛 第i头牛跳舞花费a_i 最大时间为T 求不超过时间T的前提下
最少多少个舞台够使用
二分check 答案区间[1,n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| bool check(int mid){
priority_queue<int,vector<int>,greater<int>>heap;
for(int i=1;i<=mid;i++){
heap.push(a[i]);
}
for(int i=mid+1;i<=n;i++){
int t=hash.top();
heap.pop();
heap.push(t+a[i]);
}
while(heap.size()>1){
heap.pop();
}
if(heap.top()>s)return false;
return true;
}
int main(){
sort(a+1,a+1+n);
int l=1,r=n;
while(l<r){
int mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
}
|
P1572 计算分数
题目链接
读入字符串后 分解成n个分数
f[i]的1和-1表示符号 a[i]表示分子 b[i]表示分母
通分为Π[i] 分子带入计算
分子和分母同时除以__gcd(a,b)
b为1的时候 不输出分号和b