-1.田地丈量

分析

测试数据

4 10 10
0 0 5 5
5 -2 15 3
8 8 15 15
-2 10 3 15

UNAC：情况不完全

• max，min就是很好用

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,a,b;
    cin>>n>>a>>b;
    long long area;
    while(n--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        if(x2<=0||y2<=0||x1>=a||y1>=b){
            area+=0;
            continue;
        } 
        else if(x1<=0) x1=0;
        else if(y1<=0) y1=0;
        else if(x2>=a) x2=a;
        else if(y2>=b) y2=b;
        area+=(x2-x1)*(y2-y1);
    }
    printf("%d",area);
    return 0;
}

AC：//if(x>=0&&y>=0)

• 判断面积正负很重要
• 保证点2始终在点1的右侧

#include<iostream>
using namespace std;

int main(){
    int n,a,b;
    cin>>n>>a>>b;
    long long area=0;//initialize
    while(n--){
        int x1,y1,x2,y2;
        int x,y;
        cin>>x1>>y1>>x2>>y2;
        x=min(a,x2)-max(0,x1);
        y=min(b,y2)-max(0,y1);
        if(x>=0 && y>=0)
            area+=x*y;
    }
    cout<<area;
    return 0;
}

-2.垦田计划

分析

• 看子任务，找变量取值范围，确定变量类型

  • int

  • long long int

< hashmap>

• #include< map >

• key--value <=> i -- 9

• e.g. flag[ i ] = 9 ;

• e.g.2. flag[ ti[ i ] ] += ci[ i ] ;

• 时间复杂度O（1）

• 如果用数组O（n）

AC：

#include<iostream>
#include<map>
using namespace std;
int n,k,mx=0;
long long int m;
map<int,int> flag,ti,ci;

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>ti[i]>>ci[i];
        mx=max(mx,ti[i]);
        flag[ti[i]]+=ci[i];//哈希映射
    }
    //先输入，再运算
    for(int i=mx;i>0;i--){
        if(mx==k) break;
        if(m>flag[i]){
            m-=flag[i];
            flag[i-1]+=flag[i];//精髓
            mx--;
        }
        else break;
    }
    cout<<mx;
    return 0;
}