大一合宿--c++優先キューpriority_queue
ゆうせんキュー
テーマ1:P 1537
テーマ2:P 1688
テーマ3:P 1689
テーマ4:P 355
テーマ5:P 1692
テーマ6:P 1691
テーマ7:P 1690
テーマ1:P 1537
#include
using namespace std;
struct _people
{
int num;
int t;
};
struct cmp1
{
bool operator()(_people a,_people b)
{
if(a.t!=b.t)
return a.t>b.t;
else
return a.num>b.num;
}
};
int main()
{
int n;
struct _people peo;
priority_queue<_people,vector<_people>,cmp1>que;
queue<_people>SAVE;
cin >> n;
for(int i=1;i<=n;i++)
{
peo.num=i;
cin >> peo.t;
que.push(peo);
}
for(int i=1;i<=n;i++)
{
if(i==1)
{
cout << que.top().num;
}
else
{
cout << " " << que.top().num;
}
SAVE.push(que.top());
que.pop();
}
cout << endl ;
double all=0;
while(SAVE.size()>1)
{
all+=SAVE.front().t;
int save;
save=SAVE.front().t;
SAVE.pop();
SAVE.front().t+=save;
}
double ave;
ave=all/n;
printf("%.2lf
",ave);
return 0;
}
テーマ2:P 1688
#include
using namespace std;
int main()
{
int n;
int x;
priority_queue<int,vector<int>,greater<int> >que;
cin >> n;
while(n--)
{
cin >> x;
que.push(x);
}
int ans=0;
while(que.size()>1)
{
int t;
t=que.top();
que.pop();
t+=que.top();
que.pop();
que.push(t);
ans+=t;
}
cout << ans << endl ;
return 0;
}
テーマ3:P 1689
#include
using namespace std;
int a[400005];
int b[400005];
struct _sum
{
int ai;
int bi;
long long sum;
};
struct cmp1
{
bool operator ()(_sum a,_sum b)
{
return a.sum>b.sum;
}
};
int main()
{
int n;
scanf("%d",&n);
priority_queue<_sum,vector<_sum>,cmp1>que;
for(int i=1; i<=n; i++)
{
scanf("%lld",&a[i]);
}
for(int i=1; i<=n; i++)
{
scanf("%lld",&b[i]);
}
struct _sum save;
for(int i=1;i<=n;i++)
{
save.ai=i;
save.bi=1;
save.sum=a[i]+b[1];
que.push(save);
}
for(int i=1;i<=n;i++)
{
printf("%lld
",que.top().sum);
struct _sum add;
add.ai=que.top().ai;
add.bi=que.top().bi+1;
add.sum=a[que.top().ai]+b[que.top().bi+1];
que.push(add);
que.pop();
}
return 0;
}
テーマ4:P 355
#include
using namespace std;
int main()
{
int n;
int x;
while(cin >> n)
{
priority_queue<int,vector<int>,greater<int> >que;
while(n--)
{
cin >> x;
que.push(x);
}
int ans=0;
while(que.size()>1)
{
int t;
t=que.top();
que.pop();
t+=que.top();
que.pop();
que.push(t);
ans+=t;
}
cout << ans << endl ;
}
return 0;
}
テーマ5:P 1692
#include
using namespace std;
int main()
{
int n;
while(cin >> n)
{
priority_queue<int,vector<int>,greater<int> >que;
for(int i=1;i<=n;i++)
{
int dox;
int x;
cin >> dox;
if(dox==1)
{
cin >> x;
que.push(x);
}
else if(dox==2)
{
cout << que.top() << endl ;
}
else if(dox==3)
{
que.pop();
}
}
}
return 0;
}
テーマ6:P 1691
#include
using namespace std;
int main()
{
int n;
int x;
priority_queue<int,vector<int>,greater<int> >que;
cin >> n;
while(n--)
{
cin >> x;
que.push(x);
}
long long ans=0;
while(que.size()>1)
{
int t;
t=que.top();
que.pop();
t+=que.top();
que.pop();
que.push(t);
ans+=t;
}
cout << ans << endl ;
return 0;
}
テーマ7:P 1690
#include
using namespace std;
struct _people
{
int num;
int t;
int period;
};
struct cmp1
{
bool operator()(_people a,_people b)
{
if(a.t!=b.t)
return a.t>b.t;
else
return a.num>b.num;
}
};
int main()
{
priority_queue<_people,vector<_people>,cmp1>que;
string s;
int nnum;
int tt;
int i=0;
while(cin >> s)
{
if(s[0]=='#')
break;
cin >> nnum >> tt;
que.push({nnum,tt,tt});
}
int k;
cin >> k;
struct _people change;
while(k--)
{
cout << que.top().num << endl;
change=que.top();
que.pop();
change.t+=change.period;
que.push(change);
}
return 0;
}