4.4-4.15写题记录

由于清明节及其他原因，写题不多。

图书馆借的一本书上的题目：工程分配问题，这道题是模拟题代码不难，倒是题目意思初看时不好理解，看了好几遍才明白。

#include "cstdio"
#include "cstring"
#include "cstdlib"

const int maxProject = 100;
const int maxEngineer = 20;
const int maxWeek =50;

int w[maxEngineer][maxWeek],pw[maxProject][maxWeek],app[maxProject];
int N,M,C,W;

void wrong()
{
    puts("Infeasible");
}

void judge()
{
    int i,j,k,count,st,ed,p,ok=1;

    scanf("%d%d%d",&N,&M,&C);
    W=0;
    for ( i = 0; i < N; ++i)
    {
        scanf("%d %d",&st,&ed);
        for ( j = st; i < ed; ++j)
        {
            scanf("%d",&pw[i][j]);
        }
        if(ed >; W)  ok=0;
    }

   memset(app,0,sizeof(app));

   for (i = 0; i < M; ++i)
   {
       if(scanf("%d",&count) != 1)  ok=0;
       for(j = 0; j < count; j++){

        if(scanf("%d",&p) != 1) ok=0;

        if(p < 0 || p >;= N || app[p])  ok=0;
        app[p]++;

        for(k = 0;k < W; k++){
            w[i][k] += pw[p][k];
            if(w[i][k] <0 || w[i][k] >; C) ok=0;
        }
        if(!ok) return wrong();
        for(i=0; i<N;i++)
            if(app[i] != 1) return wrong();

        puts("Fessible");

       }
   }

}

int main()
{
    int num;
    scanf("%d",&num);
    while(num--){
        memset(w,0,sizeof(w));
        memset(pw,0,sizeof(pw));

        judge();

    }
    return 0;
}

范围查询(Range)

描述

数轴上有n个点，对于任一闭区间 [a, b]，试计算落在其内的点数。

输入

第一行包括两个整数：点的总数n，查询的次数m。

第二行包含n个数，为各个点的坐标。

以下m行，各包含两个整数：查询区间的左、右边界a和b。

输出

对每次查询，输出落在闭区间[a, b]内点的个数。

Example

Input

    5 2
    1 3 7 9 11
    4 6
    7 12
    `</pre>
    Output
    <pre class="">`0
    3

限制

0 ≤ n, m ≤ 5×10⁵

对于次查询的区间[a, b]，都有a ≤ b

各点的坐标互异

各点的坐标、查询区间的边界a、b，均为不超过10^7的非负整数

时间：2 sec

内存：256 MB

#include <stdio.h>;
#include <stdlib.h>;
#include <algorithm>;
using namespace std;
#define L 500001
int A[L];

int fun(int be,int ed,int ac){
    int mid, left =be,right = ed;
    while(left <= right){
    mid = left + ((right - left) / 2);
    if (A[mid] >;= ac)   right = mid - 1;
      else left = mid + 1;         
 }
   return left;
}

int main()
{
    int m,n;
    scanf("%d %d\n",&m,&n);

    for (int i = 0; i < m; ++i)
    {
        scanf("%d",&A[i]);
    }
    sort(A,A+m);
    for (int i = 0; i < n; ++i)
    {
       int begin,end;
       scanf("%d %d",&begin,&end);

       int count;
       int rt,lt;

       rt = fun(0,m-1,end );
       lt = fun(0,m-1,begin );
       count = rt - lt;
       if(A[rt] == end) count++;
       if(count < 0)  count = 0;
       printf("%d\n",count );
    }
    return 0;
}