1. //二分算法
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1000005;
int chafen[maxn],u[maxn],t[maxn],v[maxn],n,c[maxn],m,a[maxn],ans;
bool heihei;
bool check(int now)//当前订单数
{
memset(chafen,0,sizeof(chafen));
for(int i=1;i<=now;i++){
chafen[u[i]]+=t[i];chafen[v[i]+1]-=t[i];
}
for(int i=1;i<=n;i++)
{
c[i]=c[i-1]+chafen[i];
if(c[i]>a[i])return false;
}
return true;
}
int main()
{
scanf("%d%d",&n,&m);//天数 订单数
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);//每天的教室
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&t[i],&u[i],&v[i]);//每次的订单 t为天数 2分订单数 查询到达某个订单时 是否可以借出
}
int l=1,r=n;
int now=1;
if(!check(now))
{
printf("-1\n%d",1);
return 0;
}
now=n;
if(check(now))
{
printf("0");
return 0;
}
int mid=(l+r)/2;
while(heihei==0)
{
if(check(mid))
{
l=mid;
mid=(mid+r)/2;
}
else
{
if(r==mid+1) heihei=1;
r=mid;
ans=mid;
mid=(l+mid)/2;
}
}
printf("-1\n%d",ans);
return 0;
}
by 学而 @ 2018-03-24 18:59:19
- //二分算法
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1000005;
int chafen[maxn],u[maxn],t[maxn],v[maxn],n,c[maxn],m,a[maxn],ans;
bool heihei;
bool check(int now)//当前订单数
{
memset(chafen,0,sizeof(chafen));
for(int i=1;i<=now;i++){
chafen[u[i]]+=t[i];chafen[v[i]+1]-=t[i];
}
for(int i=1;i<=n;i++)
{
c[i]=c[i-1]+chafen[i];
if(c[i]>a[i])return false;
}
return true;
}
int main()
{
scanf("%d%d",&n,&m);//天数 订单数
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);//每天的教室
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&t[i],&u[i],&v[i]);//每次的订单 t为天数 2分订单数 查询到达某个订单时 是否可以借出
}
int l=1,r=n;
int now=1;
if(!check(now))
{
printf("-1\n%d",1);
return 0;
}
now=n;
if(check(now))
{
printf("0");
return 0;
}
int mid=(l+r)/2;
while(heihei==0)
{
if(check(mid))
{
l=mid;
mid=(mid+r)/2;
}
else
{
if(r==mid+1) heihei=1;
r=mid;
ans=mid;
mid=(l+mid)/2;
}
}
printf("-1\n%d",ans);
return 0;
}
by 学而 @ 2018-03-24 19:00:08
哇 我发不出能换行的代码....
by 学而 @ 2018-03-24 19:00:59
@[程孟恩](/space/show?uid=61643)
\```
中间加代码
\```
by ViXbob @ 2018-03-24 19:02:39
请使用
` ```cpp `
` ``` `
把代码括住
by AThousandSuns @ 2018-03-24 19:37:41
帮您排了个版。。。
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1000005;
int chafen[maxn],u[maxn],t[maxn],v[maxn],n,c[maxn],m,a[maxn],ans;
bool heihei;
bool check(int now) { //当前订单数
memset(chafen,0,sizeof(chafen));
for(int i=1; i<=now; i++) {
chafen[u[i]]+=t[i];
chafen[v[i]+1]-=t[i];
}
for(int i=1; i<=n; i++) {
c[i]=c[i-1]+chafen[i];
if(c[i]>a[i])return false;
}
return true;
}
int main() {
scanf("%d%d",&n,&m);//天数 订单数
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);//每天的教室
}
for(int i=1; i<=m; i++) {
scanf("%d%d%d",&t[i],&u[i],&v[i]);//每次的订单 t为天数 2分订单数 查询到达某个订单时 是否可以借出
}
int l=1,r=n;
int now=1;
if(!check(now)) {
printf("-1\n%d",1);
return 0;
}
now=n;
if(check(now)) {
printf("0");
return 0;
}
int mid=(l+r)/2;
while(heihei==0) {
if(check(mid)) {
l=mid;
mid=(mid+r)/2;
} else {
if(r==mid+1) heihei=1;
r=mid;
ans=mid;
mid=(l+mid)/2;
}
}
printf("-1\n%d",ans);
return 0;
}
```
by Siyuan @ 2018-03-24 20:00:00
@[siyuan](/space/show?uid=49725) 谢谢 特别感谢 大谢特谢
教室里默默打代码的高中生感受到了世界 对它~~（single dog）~~的爱
by 学而 @ 2018-03-24 20:07:55
@[ViXbob](/space/show?uid=50971) 十分感谢
by 学而 @ 2018-03-24 20:08:41
@[AThousandSuns](/space/show?uid=72118) 感谢*n
by 学而 @ 2018-03-24 20:09:32
然而你们竟然不知道dev-c++里Ctrl+shift+A就能自动排版。。。。
by Siyuan @ 2018-03-24 20:50:57