T1：奶牛晒衣服
加工生产调度emmm写他的时候突然想起来学长带着做题时有一个什么产工件的题，其中有一个题解用洗衣机和烘干机模拟 A B 工程。那时候我以为作者大抵是闲的，现在看到此题才明白过来
另外复习一下优先队列
priority_queue<int> a;//默认小根（大顶）
priority_queue<int, vector<int>, less<int> > a; //同上
priority_queue<int, vector<int>, greater<int> > c;//这样就是大根（小顶）查看代码
#include<bits/stdc++.h>
using namespace std;
int n,a,b;
priority_queue<int> c;
int main()
{
scanf("%d%d%d",&n,&a,&b);
for(int i=0,j;i<n;i++)
{
scanf("%d",&j);
c.push(j);
}
int t=0;
while(c.top()>a*t)
{
int now=c.top();
c.pop();
t++;
c.push(now-b);
}
printf("%d\n",t);
return 0;
}T2：雷达装置
查看代码
#include<bits/stdc++.h>
using namespace std;
int n,ans=0;
double d,x[10002],y[10002],temp;
struct node{
double l,r;
}a[10002];
double cmp(node w,node e){
return w.r<e.r;
}
int main(){
cin>>n>>d;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
if(y[i]>d){
cout<<"-1"<<endl;
return 0;
}
a[i].l=x[i]-sqrt(d*d-y[i]*y[i]);
a[i].r=x[i]+sqrt(d*d-y[i]*y[i]);
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
if(i==1) temp=a[i].r,ans++;
else if(temp>a[i].l) continue;
else temp=a[i].r,ans++;
}
cout<<ans<<endl;
return 0;
}T3：畜栏预定
查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,ans[600000],num;
struct node
{
int s,p;
}a[100001],b[100001];
int cmp(node x,node y)
{
return x.s<y.s;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].s,&b[i].s);
a[i].p=b[i].p=i;
}
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1,cmp);
int j=1;
for(int i=1;i<=n;i++)
{
if(j<=n)j++;
if(!ans[b[i].p])ans[b[i].p]=++num;
while(a[j].s<=b[i].s&&j<=n)j++;
ans[a[j].p]=ans[b[i].p];
}
printf("%d\n",num);
for(int i=1;i<=n;i++)
{
printf("%d\n",ans[i]);
}
return 0;
}T4：荷马史诗
查看代码
#include<bits/stdc++.h>
#define LL long long
using namespace std;
struct node {
LL x,v;
bool operator < (const node &aa) const {
return x>aa.x || (x==aa.x && v>aa.v);
}
};
priority_queue<node> q;
int n,m;
int main() {
LL x;
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++) {
scanf("%lld",&x);
q.push((node) {
x,0
});
}
while ((n-1)%(m-1)!=0) {
++n;
q.push((node) {
0LL,0
});
}
LL ans=0;
while (q.size()>1) {
LL sum=0,d=0;
for (int i=1; i<=m; i++)
if (!q.empty()) {
node now=q.top();
q.pop();
sum+=now.x;
if (now.v>d) d=now.v;
}
ans+=sum;
q.push((node) {
sum,++d
});
}
cout<<ans<<endl<<q.top().v;
return 0;
}