?
A
分析
排序+中位數性質
AC代碼
#include<iostream>
using namespace std;
int a[100010];
void sort(int l,int r)
{
if(l>=r) return ;
int i=l-1,j=r+1,mid=a[l+r>>1];
while(i<j)
{
do i++;while(mid>a[i]);
do j--;while(mid<a[j]);
if(i<j) swap(a[i],a[j]);
}
sort(l,j);
sort(j+1,r);
}
int main()
{
int n,s=0;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
sort(0,n-1);
for(int j=0;j<n;j++)
s+=abs(a[j]-a[n/2]);
cout<<s<<endl;
return 0;
}
手搓快排玩玩，嘿嘿????
B
分析
這里要我們求連續不小于f塊地的柵欄所圍的奶牛的平均數的最大值，
根據要求可知，所求平均數最大值一定在每單個區域奶牛數量的最大值和最小值之間，
那么現在就可以很明顯的看出，這是一個二分查找左區間的右邊界點的題目，
我們只需從每單個區域奶牛數量的最大值和最小值之間二分查找答案即可，
AC代碼
#include<iostream>
using namespace std;
const int N=100010;
int n,m,c[N];
double sum[N];
bool check(double avg)
{
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+c[i]-avg;//計算前綴和
double minv=0;//設定最小值
for(int i=0,j=m;j<=n;j++,i++)
{
minv=min(minv,sum[i]);//找最優極小值
if(sum[j]>=minv) return true;//進行判斷
}
return false;//如果所有的都不滿足，那么這個平均數就一定不滿足
}
int main()
{
scanf("%d%d",&n,&m);
double l=0,r=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
r = max(r, (double)c[i]);
}
while(r-l>1e-5)
{
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
printf("%d\n ",int(r*1000));
return 0;
}
C
分析
兩邊的牛高 中間的牛矮資料范圍很大所以我們可以使用差分但是題目最高又限制了最高的牛所以我們還需要查重
?
AC代碼
#include<iostream>
#include<set>
using namespace std;
int main()
{
int n,p,h,m;
int hi[10010],c[10010];
cin>>n>>p>>h>>m;
// hi[1]=h;
set<pair<int ,int >>e;
for(int i=0,a,b;i<m;i++)
{
cin>>a>>b;
if(a>b) swap(a,b);
if(!e.count({a,b}))
{
e.insert({a,b});
hi[a+1]--;
hi[b]++;
}
}
for (int i = 1; i <= n; i++)
{
hi[i]+=hi[i-1];
cout << h+hi[i] << endl;
}
return 0;
}
D
分析
炸彈的范圍是R，可以看成每個城市的影響范圍是R，找出最多的重疊部分就可以了
用到二維前綴和
AC代碼
#include <iostream>
#include <algorithm>
using namespace std;
const int M=5010;
int n,m,s[M][M];
int main()
{
int cnt, R;
cin >> cnt >> R;
R = min(5001, R);
n = m = 5001;
while (cnt -- )
{
int x, y, w;
cin >> x >> y >> w;
x ++, y ++ ;
s[x][y] += w;
}
for(int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
s[i][j]+= s[i-1][j] + s[i][j-1]-s[i-1][j-1];
int res=0;
for(int i=R;i<=n;i++)
for(int j=R;j<=m;j++)
res=max(res,s[i][j]-s[i-R][j]-s[i][j-R]+s[i-R][j-R]);
cout<<res<<endl;
return 0;
}
E
分析
以每個矩形的高度為準，向兩邊擴展，直到遇到比它矮的為止
每個矩形的高度都是>=0的，為了使得每個矩形的兩側都有矮于它的矩形，
所以往兩側放了兩個-1的矩形h[0] = h[n + 1] = -1;
由于有-1矩形的存在，不會有任何矩形的高度 hh 滿足 ?1>=h?1>=h，所以堆疊不會空
因此可以省略堆疊中是否有元素的判斷條件tt >= 0
AC代碼
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int h[N],q[N],l[N],r[N];
int main()
{
int n;
while(cin>>n, n)
{
for(int i = 1; i <= n; i ++)
cin>>h[i];
h[0]=h[n+1]=-1;
int tt=-1;
q[++tt]=0;
for(int i=1;i<=n;i++)
{
while(h[q[tt]]>=h[i]) tt--;
l[i]=i-q[tt];
q[++tt]=i;
}
tt=0;
q[0]=n+1;
for(int i=n;i;i --)
{
while(h[q[tt]]>=h[i]) tt--;
r[i]=q[tt]-i;
q[++tt]=i;
}
long long res=0;
for(int i=1;i<=n;i ++)
res=max(res,(long long )h[i]*(l[i]+r[i]-1));
cout<<res<<endl;
}
return 0;
}
F
分析
題目中的操作都是在資料的最后一位所以可以用對頂堆疊就是top對著top的堆疊
AC代碼
#include<iostream>
#include<string>
#define N 1000010
using namespace std;
int sum[N],f[N],sul[N],sur[N],t1,t2;
int main()
{
string a;
int n,x;
f[0]=-0x3f3f3f3f;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a;
if(a=="I")
{
cin>>x;
sul[++t1]=x;
sum[t1] = sum[t1 - 1] + sul[t1];
f[t1] = max(f[t1 - 1], sum[t1]);
}
if(a=="D")
if (t1) t1--;
if(a=="L") if (t1) sur[++t2] = sul[t1--];
if(a=="R")
if (t2)
{
sul[++t1] = sur[t2--];
sum[t1] = sum[t1 - 1] + sul[t1];
f[t1] = max(f[t1 - 1], sum[t1]);
}
if(a=="Q")
{
cin>>x;
cout<<f[x]<<endl;
}
}
// for(int i=0;i<10;i++)
// cout<<"*"<<sul[i]<<"*/*"<<sur[i]<<"*";
return 0;}
G
分析
入隊
先判斷小組是否有人，如果沒人，將小組編號加入 pointer 中
將新人加入她所在的小組
出隊
先判斷pointer指向的第一個小組還有沒有人
——如果沒人，就出隊第一個小組編號，去判斷第二個
然后正常出隊即可
AC代碼
#include<iostream>
#include<queue>
#include<string>
using namespace std;
const int N=1010;
int t[N*N];
int main()
{
int n,q=1;
while(cin>>n&&n)
{
printf("Scenario #%d\n",q++);
for(int i=0;i<n;i++)
{
int cnt;
cin>>cnt;
while(cnt--)
{
int x;
cin>>x;
t[x]=i;
}
}
queue<int >team;
queue<int >person[N];
string ss;
while(cin>>ss&&ss!="STOP")
{
if(ss=="ENQUEUE")
{
int x;
cin>>x;
int id=t[x];
if(person[id].empty()) team.push(id);//如果無這小組就加到后面
person[id].push(x);
}
if(ss=="DEQUEUE")
{
int id=team.front();
cout<<person[id].front()<<endl;
person[id].pop();
if(person[id].empty()) team.pop();//如果這小組空了就刪了
}
}
puts("");
}
return 0;
}
H
分析
目標是s[i] - s[i-j], j = 1, 2, ..., m 的最大值，等價于求 s[i-j], j = 1, 2, ..., m 的最小值，即 s 的下標取區間 [i-m, i-1] 內的最小值，即滑動視窗求最小值問題，可以用單調佇列來優化，
AC代碼
#include<iostream>
#include<deque>
#include<climits>
using namespace std;
const int N=3e5+10;
int n,m;
deque<int>q;
long long s[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s[i];
s[i]+=s[i-1];
}
long long res=INT_MIN;
q.push_back(0);
for(int i=1;i<=n;i++)
{
if(!q.empty()&&i-q.front()>m)
{
q.pop_front();
}
res=max(res,s[i]-s[q.front()]);
while (!q.empty() && s[q.back()] >= s[i])
q.pop_back();
q.push_back(i);
}
cout<<res<<endl;
return 0;
}
?
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/421334.html
標籤：其他
下一篇：模擬退火演算法詳解